{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Duplicate Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #two-pointers #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #双指针 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找重复数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含&nbsp;<code>n + 1</code> 个整数的数组&nbsp;<code>nums</code> ，其数字都在&nbsp;<code>[1, n]</code>&nbsp;范围内（包括 <code>1</code> 和 <code>n</code>），可知至少存在一个重复的整数。</p>\n",
    "\n",
    "<p>假设 <code>nums</code> 只有 <strong>一个重复的整数</strong> ，返回&nbsp;<strong>这个重复的数</strong> 。</p>\n",
    "\n",
    "<p>你设计的解决方案必须 <strong>不修改</strong> 数组 <code>nums</code> 且只用常量级 <code>O(1)</code> 的额外空间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,4,2,2]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,3,4,2]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums.length == n + 1</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= n</code></li>\n",
    "\t<li><code>nums</code> 中 <strong>只有一个整数</strong> 出现 <strong>两次或多次</strong> ，其余整数均只出现 <strong>一次</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>进阶：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如何证明 <code>nums</code> 中至少存在一个重复的数字?</li>\n",
    "\t<li>你可以设计一个线性级时间复杂度 <code>O(n)</code> 的解决方案吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-duplicate-number](https://leetcode.cn/problems/find-the-duplicate-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-duplicate-number](https://leetcode.cn/problems/find-the-duplicate-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,2,2]', '[3,1,3,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        for path in paths:\n",
    "            s = path.split(' ')\n",
    "            root = s[0]\n",
    "            for file in s[1:]:\n",
    "                name, content = file.split('(')\n",
    "                if content not in mp:\n",
    "                    mp[content] = [root+'/'+name]\n",
    "                else:\n",
    "                    mp[content].append(root+'/'+name)\n",
    "        res = []\n",
    "        for key in mp:\n",
    "            if len(mp[key]) >= 2:\n",
    "                res.append(mp[key])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = {}  #定义一个字典\n",
    "        for p in paths:  #对目录进行遍历\n",
    "            s = []\n",
    "            s = p.split(' ')  #将字符串s按空格分开，其中s[0]表示目录，\n",
    "            #print(s)\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split(\"(\")  #将文件名和内容分开，这里直接用\"(\"分开即可\n",
    "                if key not in hashtag:\n",
    "                    hashtag[key] = [s[0] + '/' + t]\n",
    "                else:\n",
    "                    hashtag[key].append(s[0] + '/' + t)  #将内容相同的文件及其对应的目录储存\n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hash={}\n",
    "        n=len(paths)\n",
    "        for i in range(n):\n",
    "            s=paths[i].split(\" \")\n",
    "            for j in range(1,len(s)):\n",
    "                path,key=s[j].split(\"(\")\n",
    "                if key not in hash:\n",
    "                    hash[key]=[s[0]+\"/\"+path]\n",
    "                else:\n",
    "                    hash[key].append(s[0]+\"/\"+path)\n",
    "        res=[]\n",
    "        for key in hash:\n",
    "            if len(hash[key])>=2:\n",
    "                res.append(hash[key])\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = {}  #定义一个字典\n",
    "        for p in paths:  #对目录进行遍历\n",
    "            s = []\n",
    "            s = p.split(' ')  #将字符串s按空格分开，其中s[0]表示目录，\n",
    "            #print(s)\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split(\"(\")  #将文件名和内容分开，这里直接用\"(\"分开即可\n",
    "                if key not in hashtag:\n",
    "                    hashtag[key] = [s[0] + '/' + t]\n",
    "                else:\n",
    "                    hashtag[key].append(s[0] + '/' + t)  #将内容相同的文件及其对应的目录储存\n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hash={}\n",
    "        n=len(paths)\n",
    "        for i in range(n):\n",
    "            s=paths[i].split(\" \")\n",
    "            for j in range(1,len(s)):\n",
    "                path,key=s[j].split(\"(\")\n",
    "                if key not in hash:\n",
    "                    hash[key]=[s[0]+\"/\"+path]\n",
    "                else:\n",
    "                    hash[key].append(s[0]+\"/\"+path)\n",
    "        res=[]\n",
    "        for key in hash:\n",
    "            if len(hash[key])>=2:\n",
    "                res.append(hash[key])\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        aux = {}\n",
    "        for path in paths:\n",
    "            values = path.split(\" \")\n",
    "            for i in range(1,len(values)):\n",
    "                num = values[i].split('(')\n",
    "                num[1] = num[1].replace(')','')\n",
    "                l = values[0] + '/' + num[0]\n",
    "                if num[1] in aux:\n",
    "                    aux[num[1]].append(l)\n",
    "                else:\n",
    "                    aux[num[1]] = [l]\n",
    "        ret = []\n",
    "        for key in aux.keys():\n",
    "            if len(aux[key]) > 1:\n",
    "                ret.append(aux[key])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        duplicate = {}\n",
    "        for line in paths:\n",
    "            adress = line.split(\" \")[0]\n",
    "            content = line.split(\" \")[1:]\n",
    "            for cnt in content:\n",
    "                cnt2 = cnt.split('(')[1]\n",
    "                cnt1 = cnt2.split(')')[0]\n",
    "                if cnt1 in duplicate:\n",
    "                    duplicate[cnt1].append(adress+'/'+cnt.split('(')[0])\n",
    "                else:\n",
    "                    duplicate[cnt1] = [adress+'/'+cnt.split('(')[0]]\n",
    "        res = []\n",
    "        for k,value in duplicate.items():\n",
    "            if len(value)>1:\n",
    "                res.append(value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for i in paths:\n",
    "            a = i.split(' ')\n",
    "            for j in a:\n",
    "                b = j.split('(')\n",
    "                if len(b) < 2:\n",
    "                    continue\n",
    "                if not b[1] in d:\n",
    "                    d[b[1]] = [a[0]+'/'+b[0]]\n",
    "                else:\n",
    "                    d[b[1]].append(a[0]+'/'+b[0])\n",
    "        c = []\n",
    "        for k,v in d.items():\n",
    "            if len(v) > 1:\n",
    "                c.append(v)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        for content in paths:\n",
    "            path, *files = content.split(' ')\n",
    "            for f in files:\n",
    "                fn, content = f.split('(')\n",
    "                content = content[:-1]\n",
    "                if content not in mp:\n",
    "                    mp[content] = []\n",
    "                mp[content].append(f'{path}/{fn}')\n",
    "        ret = []\n",
    "        for k, v in mp.items():\n",
    "            if len(v) > 1:\n",
    "                ret.append(v)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        def parse(strs):\n",
    "            strs_list = strs.split(' ')\n",
    "            path = strs_list[0]\n",
    "            name_contxt_list = strs_list[1:]\n",
    "            path_list = []\n",
    "            contxt_list = []\n",
    "            for name_contxt in name_contxt_list:\n",
    "                name,contxt = name_contxt.split('(')\n",
    "                file_path = path+'/'+name\n",
    "                path_list.append(file_path)\n",
    "                contxt_list.append(contxt)\n",
    "            return path_list,contxt_list\n",
    "        dicts = {}\n",
    "        for strs in paths:\n",
    "            file_path_list,contxt_list = parse(strs)\n",
    "            for i in range(len(file_path_list)):\n",
    "                file_path = file_path_list[i]\n",
    "                contxt = contxt_list[i]\n",
    "                if contxt in dicts.keys():\n",
    "                    dicts[contxt].append(file_path)\n",
    "                else:\n",
    "                    dicts[contxt] = [file_path]\n",
    "        ans = []\n",
    "        for key in dicts.keys():\n",
    "            if len(dicts[key])>1:\n",
    "                ans.append(dicts[key])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        aux = {}\n",
    "        for path in paths:\n",
    "            values = path.split(\" \")\n",
    "            for i in range(1,len(values)):\n",
    "                name_cont = values[i].split(\"(\")\n",
    "                name_cont[1] = name_cont[1].replace(\")\",\"\")\n",
    "                l = values[0] + \"/\" + name_cont[0]\n",
    "                if name_cont[1] in aux:\n",
    "                    aux[name_cont[1]].append(l)\n",
    "                else:\n",
    "                    aux[name_cont[1]] = [l]\n",
    "        res=[]\n",
    "        for key in aux.keys():\n",
    "            if len(aux[key]) > 1:\n",
    "                res.append(aux[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = defaultdict(list)\n",
    "        for p in paths:\n",
    "            s = p.split(' ')\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split('(')\n",
    "                hashtag[key].append(s[0] + '/' + t)\n",
    "        \n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        map = {}\n",
    "        for st in paths:\n",
    "            name = st.split()\n",
    "            root = name[0]\n",
    "            for i in range(1, len(name)):\n",
    "                name_list = name[i].split(\"(\")\n",
    "                content = name_list[1].replace(\")\", \"\")\n",
    "                map[content] = map.get(content, [])\n",
    "                map.get(content).append(root + \"/\" + name_list[0])\n",
    "        for item in map:\n",
    "            if len(map.get(item)) > 1:\n",
    "                res.append(map.get(item))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        fileDict = dict()\n",
    "        for path in paths:\n",
    "            pathArr = path.strip().split(\" \")\n",
    "            for i, file in enumerate(pathArr[1:]):\n",
    "                fileArr = file.split(\"(\")\n",
    "                content = fileArr[1][:-1]\n",
    "                fileDict.setdefault(content, []).append(pathArr[0] + \"/\" + fileArr[0])\n",
    "                # tmpList = fileDict.get(content, [])\n",
    "                # tmpList.append(pathArr[0] + \"/\" + fileArr[0])\n",
    "                # fileDict[content] = tmpList\n",
    "        res = []\n",
    "        for value in fileDict.values():\n",
    "            if len(value) > 1:\n",
    "                res.append(value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\r\n",
    "class Solution:\r\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\r\n",
    "        content_map={}\r\n",
    "   \r\n",
    "        for path in paths:\r\n",
    "            dir,*files=path.split(' ')\r\n",
    "            for file in files:\r\n",
    "                for i in range(L:=len(file)-1,-1,-1):\r\n",
    "                    if file[i]=='(':\r\n",
    "                        content=file[i+1:L]\r\n",
    "                        sames=content_map.setdefault(content,[])\r\n",
    "                        sames.append(dir+'/'+file[:i])\r\n",
    "                        break\r\n",
    "        ret=[]\r\n",
    "        for v in content_map.values():\r\n",
    "            if len(v)>1:\r\n",
    "                ret.append(v)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        cp_map = {}\n",
    "        for i in range(len(paths)):\n",
    "            path_items = paths[i].split(' ')\n",
    "            dir = path_items[0]\n",
    "            for j in range(1, len(path_items)):\n",
    "                item = path_items[j]\n",
    "                c_start, c_end = item.find('('), item.find(')')\n",
    "                file_name = item[0: c_start]\n",
    "                file_content = item[c_start+1:c_end]\n",
    "                path = dir + '/' + file_name\n",
    "                values = cp_map.get(file_content, [])\n",
    "                values.append(path)\n",
    "                cp_map[file_content] = values\n",
    "        ret = []\n",
    "        for c, files in cp_map.items():\n",
    "            if len(files) >= 2:\n",
    "                ret.append(files)\n",
    "        return ret\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/find-duplicate-file-in-system/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        m = {}\n",
    "        for path in paths:\n",
    "            if path == \"\":\n",
    "                continue\n",
    "            row = path.split(\" \")\n",
    "            if row.__len__() < 2:\n",
    "                continue\n",
    "            folder, files = row[0], row[1:]\n",
    "            for file in files:\n",
    "                tmp = file.split(\"(\")\n",
    "                if tmp.__len__() != 2:\n",
    "                    continue\n",
    "                filename = tmp[0]\n",
    "                content = tmp[1][:-1]\n",
    "                if content not in m.keys():\n",
    "                    m[content] = []\n",
    "                m[content].append(\"{}/{}\".format(folder, filename))\n",
    "        ans = []\n",
    "        for content, ps in m.items():\n",
    "            if ps.__len__() <= 1:\n",
    "                continue\n",
    "            ans.append(ps)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp=defaultdict(list)\n",
    "        for content in paths:\n",
    "            path, *files=content.split(' ')\n",
    "            for f in files:\n",
    "                fn, content = f.split('(')\n",
    "                content=content[:-1]\n",
    "                mp[content].append(f'{path}/{fn}')\n",
    "        ret = []\n",
    "        for k,v in mp.items():\n",
    "            if len(v)>1:\n",
    "                ret.append(v)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tmp = defaultdict(list)\n",
    "\n",
    "        for f in paths:\n",
    "            f = f.split(\" \")\n",
    "            for t in f[1:]:\n",
    "                t = t.split(\"(\")\n",
    "                tmp[t[1]].append(f[0] + \"/\" + t[0])\n",
    "\n",
    "        return [i for i in tmp.values() if len(i) > 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            info = path.split()\n",
    "            for i in range(1, len(info)):\n",
    "                sub_info = info[i].strip(\")\").split(\"(\")\n",
    "                res[sub_info[1]].append(info[0] + \"/\" + sub_info[0])\n",
    "        return [l for _, l in res.items() if len(l) > 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mulu = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            wenjian  = path.split(\" \")\n",
    "            n = len(wenjian)\n",
    "            for i in range(1, n):\n",
    "                ind = wenjian[i].index(\"(\")\n",
    "                name = wenjian[i][:ind]\n",
    "                content = wenjian[i][ind+1:-1]\n",
    "                mulu[content].append(wenjian[0] + \"/\" + name)\n",
    "        ans = list()\n",
    "        for mu in mulu.keys():\n",
    "            if len(mulu[mu]) > 1:\n",
    "                ans.append(mulu[mu])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for path in paths:\n",
    "            f = path.split()\n",
    "            dir_path = f[0]\n",
    "            n = len(f)\n",
    "            for i in range(1,n):\n",
    "                F = f[i]\n",
    "                idx = F.find(\"(\")\n",
    "                file_name = F[:idx]\n",
    "                file_content = F[idx:]\n",
    "                file_path = dir_path + \"/\" + file_name\n",
    "                d[file_content].append(file_path)\n",
    "\n",
    "        ans = []\n",
    "        for k,v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths):\n",
    "        import re\n",
    "        map = {}\n",
    "        ret = {}\n",
    "        res = []\n",
    "        for i in paths:\n",
    "\n",
    "            temp = i.split(\" \")\n",
    "            for j in temp[1:]:\n",
    "                match = re.search(r'(.*?)\\((.*?)\\)', j)\n",
    "                key = temp[0] + '/' + match.group(1)\n",
    "                value = match.group(2)\n",
    "                map[key] = value\n",
    "\n",
    "        for k, v in map.items():\n",
    "            if v not in ret:\n",
    "                ret[v] = [k]\n",
    "            else:\n",
    "                ret[v].append(k)\n",
    "        for i in ret.values():\n",
    "            if len(i)>=2:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dic,re={},[]\n",
    "        lenre=0\n",
    "        for i in paths:\n",
    "            d=i.split(' ')\n",
    "            for j in d[1:]:\n",
    "                j=j.split('(')\n",
    "                if j[1] in dic:\n",
    "                    re[dic[j[1]]].append(d[0]+'/'+j[0])\n",
    "                else:\n",
    "                    dic[j[1]]=lenre\n",
    "                    re.append([d[0]+'/'+j[0]])\n",
    "                    lenre+=1\n",
    "        re=[i for i in re if len(i)>1]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "      paths_list = list()\n",
    "\n",
    "      txt_dir = dict()\n",
    "      for val in paths:\n",
    "          paths_list = val.split()\n",
    "          tem_dir = paths_list[0]\n",
    "          for j, path in enumerate(paths_list):\n",
    "              if j > 0:\n",
    "                  text_list = path.split(\"(\")\n",
    "                  root_path = tem_dir + \"/\" + text_list[0]\n",
    "                  txt_dir[root_path] = text_list[1].strip(\")\")\n",
    "      val_set = set(txt_dir.values())\n",
    "      res = []\n",
    "      if len(val_set) == len(txt_dir):\n",
    "          return res\n",
    "      for val_d in val_set:\n",
    "          val_list = []\n",
    "          for item_value in txt_dir:\n",
    "              if txt_dir[item_value] == val_d:\n",
    "                  val_list.append(item_value)\n",
    "          if len(val_list) > 1:\n",
    "              res.append(val_list)\n",
    "\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        result = []\n",
    "        for i in paths:\n",
    "            if \" \" in i:\n",
    "                j = i.split()\n",
    "                j = [j[0] + \"/\" +k for k in j[1:]]\n",
    "                print(j)\n",
    "                result.extend(j)\n",
    "            else:\n",
    "                result.append(i)\n",
    "        all_result = {}\n",
    "        for i in result:\n",
    "            value, key = i.split(\"(\")\n",
    "            print(key, value)\n",
    "            if all_result.get(key):\n",
    "                all_result[key].append(value)\n",
    "            else:\n",
    "                all_result[key] = [value]\n",
    "\n",
    "        result = []\n",
    "        for key in all_result.keys():\n",
    "            if len(all_result[key]) > 1:\n",
    "                result.append(all_result[key])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import re\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        all_paths = []\n",
    "        for path in paths:\n",
    "            context_index = [s.start() for s in re.finditer('\\(', path)]\n",
    "            for i in range(len(context_index)):\n",
    "                all_paths.append(path.split()[0] + '/' + path.split()[1+i])\n",
    "\n",
    "        dic = {}\n",
    "        for path in all_paths:\n",
    "            context = path[path.index('(')+1:path.index(')')]\n",
    "\n",
    "            tmp = '/'.join(path[:path.index('(')].split())\n",
    "            if not dic.get(context):\n",
    "                dic[context] = [tmp]\n",
    "            else:\n",
    "                dic[context].append(tmp)\n",
    "\n",
    "        res = []\n",
    "        for key in dic.keys():\n",
    "            if len(dic[key]) > 1:\n",
    "                res.append(dic[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        count = {}\n",
    "        dic = {}\n",
    "        for line in paths:\n",
    "            p = line.split(\" \")\n",
    "            root = p[0]\n",
    "            files = p[1:]\n",
    "            for file in files:\n",
    "                d = file[:-1].split(\"(\")\n",
    "                file_name = d[0]\n",
    "                content = d[1]\n",
    "                if content in count:\n",
    "                    count[content] += 1\n",
    "                    dic[content].append(root+\"/\"+file_name)\n",
    "                else:\n",
    "                    count[content] = 1\n",
    "                    dic[content] = [root+\"/\"+file_name]\n",
    "        res = []\n",
    "        for content in count:\n",
    "            if count[content] >1:\n",
    "                res.append(dic[content])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            parts = path.split()\n",
    "            root = parts[0]\n",
    "            for i in range(1, len(parts)):\n",
    "                left_parenthesis = parts[i].index('(')\n",
    "                file_name = parts[i][:left_parenthesis]\n",
    "                content = parts[i][left_parenthesis + 1: -1]\n",
    "                if content in d.keys():\n",
    "                    d[content].append(root + '/' + file_name)\n",
    "                else:\n",
    "                    d[content] = [root + '/' + file_name]\n",
    "        ans = []\n",
    "        for k, v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        print(ans)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: [str]) -> [[str]]:\n",
    "        fileContent={}\n",
    "        for i in paths:\n",
    "            path=i.split()[0]\n",
    "            files=i.split()[1:]\n",
    "            \n",
    "            for f in files:\n",
    "                fname,content=f.split('(')\n",
    "                content=content[:-1]\n",
    "                if content in fileContent:\n",
    "                    fileContent[content].append(path+'/'+fname)\n",
    "                else:\n",
    "                    fileContent[content]=[path+'/'+fname]\n",
    "                \n",
    "        r=[]\n",
    "        for key,val in fileContent.items():\n",
    "            if len(val)>1:\n",
    "                r.append(val)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        con2path = {}\n",
    "        for file_content in paths:\n",
    "            file_list = file_content.split(\" \")\n",
    "            file_prefix = file_list[0]\n",
    "            for i in range(len(file_list) - 1):\n",
    "                [filename, filedata] = self.splitFileNameContent(file_list[i + 1])\n",
    "                if filedata in con2path:\n",
    "                    con2path[filedata].append(f\"{file_prefix}/{filename}\")\n",
    "                else:\n",
    "                    con2path[filedata] = [f\"{file_prefix}/{filename}\"]\n",
    "        result = []\n",
    "        for e in con2path:\n",
    "            if len(con2path[e]) > 1:\n",
    "                result.append(con2path[e])\n",
    "        return result\n",
    "\n",
    "    def splitFileNameContent(self, data: str) -> List[str]:\n",
    "        fi = data.find('(')\n",
    "        return [data[0:fi], data[fi + 1:-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        my_dic={}\n",
    "        for  x  in paths:\n",
    "            s=x.split(' ')\n",
    "            for data in s[1:]:\n",
    "                t,val=data.split('(')\n",
    "                if val not in my_dic:\n",
    "                    my_dic[val]=[s[0]+'/'+t]\n",
    "                else:\n",
    "                    my_dic[val].append(s[0]+'/'+t)\n",
    "        res=[]\n",
    "        for x in my_dic:\n",
    "            if len(my_dic[x])>=2:\n",
    "                res.append(my_dic[x])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            arr = path.split()\n",
    "            dir = arr[0]\n",
    "            for file in arr[1:]:\n",
    "                idx = file.index('(')\n",
    "                filename = file[0:idx]\n",
    "                content = file[idx + 1: -1]\n",
    "                absolutePath = dir + '/' + filename\n",
    "                if content not in d:\n",
    "                    d[content] = [absolutePath]\n",
    "                else:\n",
    "                    d[content].append(absolutePath)\n",
    "        return [x for x in d.values() if len(x) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "        dir = []\n",
    "        for p in paths:\n",
    "            files = p.split(\" \")\n",
    "            dir.append(files)\n",
    "\n",
    "        for d in dir:\n",
    "            for f in d[1:]:\n",
    "                name,cont = f.split(\"(\")\n",
    "                mp[cont].append(d[0]+\"/\"+name)\n",
    "        ans = []\n",
    "        for k in mp.keys():\n",
    "            if len(mp[k]) > 1:\n",
    "                ans.append(mp[k])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        n = len(paths)\n",
    "        file_dict = dict()\n",
    "        for i in range(n):\n",
    "            root_file = paths[i].split(' ')\n",
    "            for j in range(1,len(root_file)):\n",
    "                file_split_content = root_file[j].split('(')\n",
    "                file_content = file_split_content[-1]\n",
    "                if file_content in file_dict:\n",
    "                    file_dict[file_content].append(root_file[0]+'/'+file_split_content[0])\n",
    "                else:\n",
    "                    file_dict[file_content] = [root_file[0]+'/'+file_split_content[0]]\n",
    "\n",
    "        key_list = list(file_dict.keys())\n",
    "        for key in key_list:\n",
    "            if len(file_dict[key])==1:\n",
    "                file_dict.pop(key)\n",
    "        return list(file_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            li = path.split(' ')\n",
    "            root = li[0]\n",
    "            for file in li[1:]:\n",
    "                content = file.split('(')[1]\n",
    "                if content in hashmap:\n",
    "                    hashmap[content].append(root + '/' + file.split('(')[0])\n",
    "                else:\n",
    "                    hashmap[content] = [root + '/' + file.split('(')[0]]\n",
    "        for i in hashmap.values():\n",
    "            if len(i) >= 2:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dict = defaultdict(list)\n",
    "        ans = []\n",
    "\n",
    "        for phase in paths:\n",
    "            phase_split = phase.split(\" \")\n",
    "            for i in range(1, len(phase_split)):\n",
    "                small_split =phase_split[i].split(\"(\")\n",
    "                content = small_split[1][:-1]\n",
    "                dict[content].append(phase_split[0] +\"/\" + small_split[0])\n",
    "        print(dict)\n",
    "\n",
    "        for key in dict:\n",
    "            if len(dict[key]) > 1:\n",
    "                ans.append(dict[key])\n",
    "\n",
    "        return ans\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            words = path.split(' ')\n",
    "            dir_path = words[0]\n",
    "            for i in range(1, len(words)):\n",
    "                word = words[i]\n",
    "                pos = word.index('(')\n",
    "                file_name = word[:pos]\n",
    "                file_content = word[pos + 1: -1]\n",
    "                file_path = dir_path + '/' + file_name\n",
    "                if file_content in d:\n",
    "                    d[file_content].add(file_path)\n",
    "                else:\n",
    "                    d[file_content] = {file_path}\n",
    "        results = []\n",
    "        for result in d.values():\n",
    "            if len(result) >= 2:\n",
    "                results.append(list(result))\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = dict()\n",
    "        res = []\n",
    "        for i in paths:\n",
    "            l = i.split(' ')\n",
    "            for j in l[1:]:\n",
    "                k = j.split('.')\n",
    "                if k[1] in d:\n",
    "                    d[k[1]].append(l[0]+'/'+k[0]+'.txt')\n",
    "                else:\n",
    "                    d[k[1]] = [l[0]+'/'+k[0]+'.txt']\n",
    "        for i in d:\n",
    "            if len(d[i])>1:\n",
    "                res.append(d[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content = {}\n",
    "        for sub_path in paths:\n",
    "            root_path = sub_path.split()[0]\n",
    "            file_names = sub_path.split()[1:]\n",
    "            for tmp_name in file_names:\n",
    "                file_name = re.match(r'\\w+\\.txt', tmp_name).group()\n",
    "                file_content = re.search(r'\\((.*)\\)', tmp_name).group(1)\n",
    "                file_path = root_path + '/' + file_name\n",
    "                if  file_content not in content:\n",
    "                    content[file_content] = {file_path}\n",
    "                else:\n",
    "                    content[file_content].add(file_path)\n",
    "        res = []\n",
    "        for tmp in content.values():\n",
    "            if len(tmp) > 1:\n",
    "                res.append(list(tmp))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        context_map_path = {}\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            words = path.split()\n",
    "            dir_path = words[0]\n",
    "            for file in words[1:]:\n",
    "                file_name,context = file[:-1].split('(')\n",
    "                if context not in context_map_path.keys():\n",
    "                    context_map_path[context] = []\n",
    "                context_map_path[context].append(dir_path+'/'+file_name)\n",
    "        for paths in context_map_path.values():\n",
    "            if len(paths) >=2 :\n",
    "                res.append(paths)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_root = {}\n",
    "        content_file = defaultdict(list)\n",
    "\n",
    "        for path in paths :\n",
    "            ss = path.split(\" \")\n",
    "            root = ss[0]\n",
    "            for s in ss[1:] :\n",
    "                file,content = s.split(\"(\")\n",
    "                content_file[content].append(root + \"/\" + file)\n",
    "                file_root[file] = root\n",
    "        \n",
    "        return (list(v for v in content_file.values() if len(v) > 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = collections.defaultdict(list)\n",
    "        for p in paths:\n",
    "            parts = p.split(' ')\n",
    "            path = parts[0]\n",
    "            for j in range(1, len(parts)):\n",
    "                name_content = parts[j].split('(')\n",
    "                file_name = name_content[0]\n",
    "                content = name_content[1][:-1]\n",
    "                content_dict[content].append(path+'/'+file_name)\n",
    "\n",
    "        return [i for i in content_dict.values() if len(i) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from collections import defaultdict\n",
    "class File:\n",
    "    def __init__(self, file_name, file_type, file_content,file_path):\n",
    "        self.file_name = file_name\n",
    "        self.file_type = file_type\n",
    "        self.file_content = file_content\n",
    "        self.file_path = file_path\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_list = defaultdict(list)\n",
    "        res = []\n",
    "        for i in  paths:\n",
    "            j = i.split()\n",
    "            for x in j[1: len(j)]:\n",
    "                k = re.split('[()]', x)\n",
    "                if (k[0].split('.')[1], k[1]) not in file_list:\n",
    "                    file_list[(k[0].split('.')[1], k[1])] = [str(j[0]) + '/' + str(k[0])]\n",
    "                else:\n",
    "                    file_list[(k[0].split('.')[1], k[1])].append(str(j[0]) + '/' + str(k[0]))\n",
    "        for key in file_list:\n",
    "            if len(file_list[key]) > 1:\n",
    "                res.append(file_list[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "\n",
    "        ans = []\n",
    "        text_dict = dict()\n",
    "        for index , data in enumerate(paths):\n",
    "            data_list = data.strip().split()\n",
    "            path = data_list[0] + '/'\n",
    "\n",
    "            for file in range(1,len(data_list)):\n",
    "                file_split = data_list[file].split('(')\n",
    "                file_name = file_split[0]\n",
    "                file_text = file_split[1].split(')')[0]\n",
    "                if file_text not in text_dict:\n",
    "                    text_dict[file_text] = [path+file_name]\n",
    "                else:\n",
    "                    text_dict[file_text].append(path+file_name)\n",
    "        print(text_dict)\n",
    "        for _, value in text_dict.items():\n",
    "            if len(value) >1:\n",
    "                ans.append(value)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for p in paths:\n",
    "            lst = p.split(' ')\n",
    "            for i in range(1, len(lst)):\n",
    "                m = re.match(r'(.+)\\((.+)\\)', lst[i])\n",
    "                x = m.group(1)\n",
    "                y = m.group(2)\n",
    "                if y not in d.keys():\n",
    "                    d[y] = []\n",
    "                d[y].append(lst[0] + '/' + x)\n",
    "        ans = []\n",
    "        for k, v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import re\n",
    "\n",
    "reg = \"(.*)\\((.*)\\)\"\n",
    "\n",
    "def parse(f):\n",
    "    m = re.match(reg, f).groups()\n",
    "    return m[0], m[1]\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        groups = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            dir, *files = path.strip().split()\n",
    "            for f in files:\n",
    "                fname, content = parse(f)\n",
    "                groups[content].append(dir+\"/\"+fname)\n",
    "        return [fs for c, fs in groups.items() if len(fs) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ret_dict = {} \n",
    "        for path in paths:\n",
    "            ps = path.split(\" \")\n",
    "            for p in ps[1:]:\n",
    "                tmps = p.split(\"(\")\n",
    "                name= tmps[0]\n",
    "                content = tmps[1].split(\")\")[0]\n",
    "\n",
    "                if content not in ret_dict:\n",
    "                    ret_dict[content] = [\"{}/{}\".format(ps[0], name)]\n",
    "                else:\n",
    "                    ret_dict[content].append(\"{}/{}\".format(ps[0], name))\n",
    "        print(ret_dict)\n",
    "        return [v for k, v in ret_dict.items() if len(v) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # 用文件内容的哈希值作为索引保存文件名; 若文件内容一致, 则它们的文件名会在一个键值对中\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        def getPathAndContent(s):\n",
    "            nonlocal d\n",
    "            if isinstance(s, list):\n",
    "                ans = []\n",
    "                for i in s:\n",
    "                    getPathAndContent(i)\n",
    "                return\n",
    "            \n",
    "            import re\n",
    "            ans = [p for p in re.split(r' |\\(|\\)', s) if len(p)]\n",
    "            path = ans.pop(0)\n",
    "            for i in range(len(ans)//2):\n",
    "                fullpath, content = path + '/' + ans[2*i], ans[2*i+1]\n",
    "                d[content].append(fullpath)\n",
    "            return\n",
    "        \n",
    "        # 记录哈希值-文件名\n",
    "        getPathAndContent(paths)\n",
    "\n",
    "        # 筛选重复文件\n",
    "        ans = []\n",
    "        for v in d.values():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parse_dir(self, directory):\n",
    "        stk = []\n",
    "        splits = directory.split('/')\n",
    "        for sp in splits:\n",
    "            if not sp:\n",
    "                continue\n",
    "            # consists only dot?\n",
    "            nodot = sp.replace('.', '')\n",
    "            if not nodot:\n",
    "                if sp == '.':\n",
    "                    continue\n",
    "                n = len(sp) - 1\n",
    "                for _ in range(n):\n",
    "                    if not stk:\n",
    "                        break\n",
    "                    stk.pop()\n",
    "            else:\n",
    "                stk.append(sp)\n",
    "        return '/'.join(stk)\n",
    "        \n",
    "    def parse_file(self, fileinfo):\n",
    "        bracidx = fileinfo.find('(')\n",
    "        filename = fileinfo[:bracidx]\n",
    "        content = fileinfo[bracidx + 1:len(fileinfo) - 1]\n",
    "        return filename, content\n",
    "\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp_content_filepaths = {}\n",
    "        for p in paths:\n",
    "            splits = p.split(' ')\n",
    "            directory = self.parse_dir(splits[0])\n",
    "            for i in range(1, len(splits)):\n",
    "                split = splits[i]\n",
    "                filename, content = self.parse_file(split)\n",
    "                filepath = '%s/%s' % (directory, filename)\n",
    "                if content not in mp_content_filepaths:\n",
    "                    mp_content_filepaths[content] = []\n",
    "                mp_content_filepaths[content].append(filepath)\n",
    "        ans = []\n",
    "        for v in mp_content_filepaths.values():\n",
    "            if len(v) >= 2:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "\n",
    "\n",
    "        dictL = defaultdict(list)\n",
    "\n",
    "        for path in paths:\n",
    "            ListT = path.split()\n",
    "            n = len(ListT)\n",
    "            for i in range(1,n):\n",
    "                str1 = ListT[i].split(\"(\")[0]\n",
    "                str2 = ListT[i].split(\"(\")[1][:-1]\n",
    "            \n",
    "                dictL[str2].append(ListT[0]+\"/\"+str1)\n",
    "        ans = []\n",
    "        for key ,val in dictL.items():\n",
    "            if len(val) > 1:\n",
    "                ans.append(list(val))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = defaultdict(list)\n",
    "        for i in paths:\n",
    "            tmp = i.split()\n",
    "            path = tmp[0]\n",
    "            file_list = tmp[1:]\n",
    "            for file in file_list:\n",
    "                index = file.index('(')\n",
    "                name = file[:index]\n",
    "                content = file[index+1:-1]\n",
    "                content_dict[content].append((path, name))\n",
    "        res = []\n",
    "        for k, v in content_dict.items():\n",
    "            if len(v) > 1:\n",
    "                tmp = []\n",
    "                for i in v:\n",
    "                    tmp.append('/'.join(i))\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = defaultdict(list)\n",
    "        for i in paths:\n",
    "            tmp = i.split()\n",
    "            path = tmp[0]\n",
    "            file_list = tmp[1:]\n",
    "            for file in file_list:\n",
    "                index = file.index('(')\n",
    "                name = file[:index]\n",
    "                content = file[index+1:-1]\n",
    "                content_dict[content].append((path, name))\n",
    "        res = []\n",
    "        for k, v in content_dict.items():\n",
    "            if len(v) > 1:\n",
    "                tmp = []\n",
    "                for i in v:\n",
    "                    tmp.append('/'.join(i))\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_dict = {}\n",
    "        for path in paths:\n",
    "            files = path.split(' ')\n",
    "            dir = files[0]\n",
    "            for file in files[1:]:\n",
    "                lidx = file.index('(')\n",
    "                ridx = file.rindex(')')\n",
    "                content = file[lidx + 1:ridx]\n",
    "                if file_dict.get(content) is None:\n",
    "                    file_dict[content] = []\n",
    "                    file_dict[content].append(dir + \"/\" + file[:lidx])\n",
    "                file_dict[content].append(dir + \"/\" + file[:lidx])\n",
    "        result = []\n",
    "        for value in file_dict.values():\n",
    "            if len(value) > 2:\n",
    "                result.append(value[1:])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        from collections import defaultdict\n",
    "        file_dict=defaultdict(list)\n",
    "        for path in paths:\n",
    "            lTemp=path.split(\" \")\n",
    "            #lTemp.reverse()\n",
    "            first=lTemp.pop(0)\n",
    "            print(lTemp)\n",
    "            for item in lTemp[0:len(lTemp)]:\n",
    "                idx=item.find(\"(\")\n",
    "                if idx!=-1:\n",
    "                    ke=item[idx:]\n",
    "                    file_dict[ke].append(first+\"/\"+item[0:idx])\n",
    "        print(file_dict)\n",
    "        res=[]\n",
    "        for v in file_dict.values():\n",
    "            if len(v)>1:\n",
    "                res.append(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dict = defaultdict(list)\n",
    "        for each in paths:\n",
    "            each_list = each.split(' ')\n",
    "            root = each_list[0]\n",
    "            files = each_list[1:]\n",
    "            for f in files:\n",
    "                file_content = f.split('(')\n",
    "                dict[file_content[1][:-1]].append([root, file_content[0]])\n",
    "        res = list()\n",
    "        for v in dict.values():\n",
    "            ans = ['/'.join(x) for x in v]\n",
    "            if len(ans) > 1:\n",
    "                res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        if not paths:\n",
    "            return\n",
    "        res = paths[0].split(' ')\n",
    "        res2 = []\n",
    "        res3 = []\n",
    "        for j in range(len(paths)):\n",
    "            res = paths[j].split(' ')\n",
    "            n = len(res)\n",
    "            for i in range(1, n):\n",
    "                res2.append(res[0] + '/' + res[i])\n",
    "        res4 = {}  \n",
    "        # res4: {'abcd': ['root/a/1.txt'], 'efsfgh': ['root/a/2.txt'], 'abdfcd': ['root/c/3.txt'], 'efggdfh': ['root/c/d/4.txt']}\n",
    "        for i, items in enumerate(res2):\n",
    "            res3 = items.split('(')\n",
    "            a = list()\n",
    "            a.append(res3[0])\n",
    "            if res3[1][:-1] in res4:\n",
    "                res4[res3[1][:-1]].append(res3[0])\n",
    "            else:\n",
    "                res4[res3[1][:-1]] = a\n",
    "        res5 = []\n",
    "        # 遍历字典的值\n",
    "        for value in res4.values():\n",
    "            if len(value) > 1:\n",
    "                res5.append(value)\n",
    "        return res5\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res4[res3[1][:-1]] = a\n",
    "        # print('res4:', res4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        # k = paths[0]\n",
    "        # list1 = k.split()\n",
    "        # l1 = list1[0] + '/' + list1[1]\n",
    "        # l2 = list1[0] + '/' + list1[2]\n",
    "        # print(l1,l2)\n",
    "\n",
    "        list2 = []\n",
    "        for i in paths:\n",
    "            list1 = i.split()\n",
    "            for j, value in enumerate(list1[1::]):\n",
    "                list2.append(list1[0] + '/' + value)\n",
    "        dict1 = {}\n",
    "        for i in list2:\n",
    "            print(i)\n",
    "            for j,v in enumerate(i):\n",
    "                if v == '(':\n",
    "                    if not dict1.get(i[j::]):\n",
    "                        dict1[i[j::]] = [i[:j]]\n",
    "                    else:                  \n",
    "                        dict1[i[j::]].append(i[:j])\n",
    "        res = []\n",
    "        for i in dict1:\n",
    "            if len(dict1[i]) > 1:\n",
    "                res.append(dict1[i])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:################哈希，O(n)\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ps = []; contents = []\n",
    "        for path in paths:\n",
    "            parts = path.split(\" \")\n",
    "            for part in parts[1:]:\n",
    "                ps.append(parts[0] + \"/\" + part.split(\"(\")[0]); contents.append(part.split(\"(\")[1])\n",
    "        ans = collections.defaultdict(list)\n",
    "        for i, p in enumerate(ps):\n",
    "            ans[contents[i]].append(p)\n",
    "        ans = [x for x in ans.values() if len(x) >= 2]\n",
    "        return ans\n",
    "\n",
    "class Solution2:################并查集，超时，O(n^2)\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ps = []; contents = []\n",
    "        for path in paths:\n",
    "            parts = path.split(\" \")\n",
    "            for part in parts[1:]:\n",
    "                ps.append(parts[0] + \"/\" + part.split(\"(\")[0]); contents.append(part.split(\"(\")[1])\n",
    "        n = len(ps); uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if contents[i] == contents[j]:\n",
    "                    uf.Union(i, j)\n",
    "        # print(uf.parents)\n",
    "        ans = collections.defaultdict(list)\n",
    "        for i, p in enumerate(uf.parents):\n",
    "            ans[uf.parents[i]].append(ps[i])\n",
    "        ans = [x for x in ans.values() if len(x) >= 2]\n",
    "        return ans\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = list(range(n))\n",
    "\n",
    "    def Find(self, x):\n",
    "        if x == self.parents[x]:\n",
    "            return x\n",
    "        return self.Find(self.parents[x])\n",
    "\n",
    "    def Union(self, x, y):\n",
    "        rootx = self.Find(x)\n",
    "        rooty = self.Find(y)\n",
    "        self.parents[x] = y\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        num_dic, path_dic = {}, {}\n",
    "        res = []\n",
    "        for st in paths:\n",
    "            file = st.split(' ')[1:]\n",
    "            for f in file:\n",
    "                index = f.index('(')\n",
    "                if f[index + 1:-1] not in num_dic.keys():\n",
    "                    num_dic[f[index + 1: -1]] = 1\n",
    "                    path_dic[f[index + 1: -1]] = [st.split(' ')[0]+'/'+ f.split('(')[0]]\n",
    "                else:\n",
    "                    num_dic[f[index + 1: -1]] += 1\n",
    "                    path_dic[f[index + 1: -1]].append(st.split(' ')[0]+'/'+ f.split('(')[0])\n",
    "        output = []\n",
    "        for key, value in num_dic.items():\n",
    "            if value > 1:\n",
    "                output.append(path_dic[key])\n",
    "        # print(num_dic)\n",
    "        # print(path_dic)\n",
    "        return output     \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            for item in i.split(\" \")[1:]:\n",
    "                tempd[i.split(\" \")[0] + \"/\" + item.split('(')[0]] = item.split('(')[1]\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            for item in i.split(\" \")[1:]:\n",
    "                tempd[i.split(\" \")[0] + \"/\" + item.split('(')[0]] = item.split('(')[1]\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempi =[]\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        temp2=[]\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            tempi = i.split(\" \")\n",
    "            for item in tempi[1:]:\n",
    "                tempd[tempi[0] + \"/\" + item.split('(')[0]] = item.split('(')[1].replace(\")\",\"\")\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            \n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ans = []\n",
    "        resul = {}\n",
    "        len_p = len(paths)\n",
    "\n",
    "        for i in range(len_p):\n",
    "            # 截取文件内容和文件名称,用空格分割\n",
    "            dirf_files = paths[i].split(' ')\n",
    "            for k in range(1,len(dirf_files)):\n",
    "                # 分割每个文件内容\n",
    "                textname = dirf_files[k].split('.')\n",
    "                #放到字典\n",
    "                #resul[(dirf_files[0],textname[0])] = textname[1]\n",
    "                if textname[1] not in resul:\n",
    "                    resul[textname[1]] = [(dirf_files[0],textname[0])]\n",
    "                else:\n",
    "                    resul[textname[1]].append((dirf_files[0],textname[0]))\n",
    "\n",
    "        for _,item in enumerate(resul.items()):\n",
    "            tmpres = []\n",
    "            if len(item[1]) > 1:\n",
    "                for i in range(len(item[1])):\n",
    "                    tmpres.append(item[1][i][0]+'/'+item[1][i][1]+'.txt')\n",
    "                ans.append(tmpres)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import hashlib\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            p = path.split()\n",
    "            rp = p[0]\n",
    "            for i in range(1, len(p)):\n",
    "                c = self.getc(p[i])\n",
    "                fn = self.getfn(p[i])\n",
    "                md5c = self.md5(c)\n",
    "                if md5c not in d:\n",
    "                    d[md5c] = [rp+\"/\"+fn]\n",
    "                else:\n",
    "                    d[md5c].append(rp+\"/\"+fn)\n",
    "        r = []\n",
    "        for k in d:\n",
    "            v = d[k]\n",
    "            if len(v) > 1:\n",
    "                r.append(d[k])\n",
    "        return r\n",
    "\n",
    "\n",
    "    def md5(self, r:str) -> str:\n",
    "        hash_obj = hashlib.md5() \n",
    "        hash_obj.update(r.encode('utf-8'))\n",
    "        \n",
    "        return hash_obj.hexdigest()\n",
    "\n",
    "    def getfn(self, s:str) -> str:\n",
    "        r = \"\"\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == '(':\n",
    "                return r\n",
    "            r += ss\n",
    "\n",
    "\n",
    "    def getc(self, s:str) -> str:\n",
    "        r = \"\"\n",
    "        f = 0\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == ')':\n",
    "                return r\n",
    "            if f == 1:\n",
    "                r += ss\n",
    "            else:\n",
    "                if ss == '(':\n",
    "                    f = 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        arr_dict = defaultdict(list)\n",
    "        res_arr = []\n",
    "\n",
    "        for path in paths:\n",
    "            arr_path = path.split()\n",
    "            file_path = arr_path[0]\n",
    "            for file_index in range(1, len(arr_path)):\n",
    "                file_name, file_content = arr_path[file_index].split('(')\n",
    "                arr_dict[file_content].append((file_path, file_name))\n",
    "\n",
    "        for x in arr_dict.values():\n",
    "            res = []\n",
    "            if len(x) > 1:\n",
    "                for t in range(len(x)):\n",
    "                    full_name = x[t][0] + '/' + x[t][1]\n",
    "                    res.append(full_name)\n",
    "                res_arr.append(res)\n",
    "\n",
    "        return res_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        word = {}\n",
    "        for i in range(len(paths)):\n",
    "            sp = (paths[i].split(\" \"))\n",
    "            for fi in range(len(sp) - 1):\n",
    "                content = re.search(\"\\(\\w+\\)\", sp[fi + 1])\n",
    "                file = re.search(\"(.*?)\\.txt\", sp[fi + 1])\n",
    "                contentw = content.group()\n",
    "                filew = sp[0] + \"/\" + file.group()\n",
    "                if word.get(contentw) == None:\n",
    "                    word[contentw] = set()\n",
    "                    word[contentw].add(filew)\n",
    "                else:\n",
    "                    word[contentw].add(filew)\n",
    "\n",
    "        ans = []\n",
    "        for k, v in word.items():\n",
    "            if len(v) >= 2:\n",
    "                ans.append(list(v))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def add(root: Optional[TreeNode]) -> Tuple:\n",
    "            if not root:\n",
    "                return None\n",
    "            key = (root.val, add(root.left), add(root.right))\n",
    "            subtree[key].append(root)\n",
    "            return key\n",
    "        \n",
    "        subtree = collections.defaultdict(list)\n",
    "        add(root)\n",
    "        ans = []\n",
    "        for _, val in subtree.items():\n",
    "            if len(val) > 1:\n",
    "                ans.append(val[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        self.res = []\n",
    "        self.dic = {}\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root: return '#'\n",
    "        tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val)\n",
    "        if tree in self.dic and self.dic[tree] == 1:\n",
    "            self.res.append(root)\n",
    "        self.dic[tree] = self.dic.get(tree, 0) + 1\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: 'TreeNode') -> 'List[TreeNode]':\n",
    "        ret = []\n",
    "        cache = {}\n",
    "        \n",
    "        def helper(root):\n",
    "            if root is None:\n",
    "                return '#'\n",
    "            else:\n",
    "                left = helper(root.left)\n",
    "                right = helper(root.right)\n",
    "                cur = str(root.val) + left + right\n",
    "                if cache.setdefault(cur, 0) == 1:\n",
    "                    ret.append(root)\n",
    "                cache[cur] += 1\n",
    "                return cur\n",
    "        helper(root)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        # 空树\n",
    "        if not root:\n",
    "            return []\n",
    "        # 线性树 - 单右枝树\n",
    "        elif not root.left:\n",
    "            has_left = False\n",
    "            while root.right:\n",
    "                root = root.right\n",
    "                if root.left:\n",
    "                    has_left = True\n",
    "                    break\n",
    "            if not has_left:\n",
    "                return []\n",
    "        # 线性树 - 单左枝树\n",
    "        elif not root.right:\n",
    "            has_right= False\n",
    "            while root.left:\n",
    "                root = root.left\n",
    "                if root.right:\n",
    "                    has_right = True\n",
    "                    break\n",
    "            if not has_right:\n",
    "                return []\n",
    "            \n",
    "        \n",
    "        def dfs(root, record):\n",
    "            \"\"\" 通过 DFS 遍历和记录树节点到哈希映射中 \"\"\"\n",
    "            if root:\n",
    "                record[root.val].append(root)\n",
    "                dfs(root.left, record)\n",
    "                dfs(root.right, record)\n",
    "        \n",
    "        def compare_subtree(root1, root2):\n",
    "            \"\"\" 通过递归比较两树是否完全相同 \"\"\"\n",
    "            if (not root1) and (not root2):\n",
    "                return True\n",
    "            elif ((not root1) or (not root2)) or (root1.val != root2.val):\n",
    "                return False\n",
    "            else:\n",
    "                return compare_subtree(root1.left, root2.left) and compare_subtree(root1.right, root2.right)\n",
    "        \n",
    "        hashmap = collections.defaultdict(list)  \n",
    "        dfs(root, hashmap)\n",
    "        \n",
    "        # 结果列表\n",
    "        result = []\n",
    "        # 遍历树节点值\n",
    "        for key in hashmap.keys():\n",
    "            nodes = hashmap[key]\n",
    "            nodes_num = len(nodes)\n",
    "            # 若值相同的节点不止一个, 则需要进行比较\n",
    "            if nodes_num > 1:\n",
    "                # 遍历值相同的节点\n",
    "                for i in range(nodes_num-1):\n",
    "                    done = False  # 是否发现过当前重复子树, 默认 False\n",
    "                    for j in range(i+1, nodes_num):\n",
    "                        # 若待比较节点非空且完全相同\n",
    "                        if nodes[i] and nodes[j] and compare_subtree(nodes[i], nodes[j]):\n",
    "                            # 若此前尚未发现过重复子树\n",
    "                            if not done:\n",
    "                                # 则添加相同子树之一到结果列表\n",
    "                                result.append(nodes[i])\n",
    "                                # 标记置为 True\n",
    "                                done = True\n",
    "                            # 其余相同子树全部置为 None\n",
    "                            nodes[j] = None\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return str(self.hash_map[\"#\"])\n",
    "        left = self.dfs(root.left)\n",
    "        right = self.dfs(root.right)\n",
    "        tree_str = left + \",\" + str(root.val) + \",\" + right\n",
    "        if tree_str not in self.hash_map:\n",
    "            self.hash_map[tree_str] = self.cnt\n",
    "            self.cnt += 1\n",
    "        t = self.hash_map[tree_str]\n",
    "        self.count[t] = self.count[t] + 1 if t in self.count else 1\n",
    "        if self.count[t] == 2:\n",
    "            self.ans.append(root)\n",
    "        return str(self.hash_map[tree_str])\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        self.cnt = 1\n",
    "        self.hash_map, self.count = {\"#\": 0}, {0:0}\n",
    "        self.ans = []\n",
    "        self.dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        self.res = []\n",
    "        self.dfs(root, {})\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root, tmp):\n",
    "        if not root:\n",
    "            return '#'\n",
    "        path = (root.val, self.dfs(root.left, tmp), self.dfs(root.right, tmp))\n",
    "        if path in tmp and tmp[path] == 1:\n",
    "            self.res.append(root)\n",
    "        tmp[path] = tmp.get(path, 0) + 1\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def findDuplicateSubtrees(self, root):\n",
    "#         d = collections.defaultdict(list)\n",
    "#         def dfs(root):\n",
    "#             if not root: return ''\n",
    "#             s = ' '.join((str(root.val), dfs(root.left), dfs(root.right)))\n",
    "#             d[s].append(root)\n",
    "#             return s\n",
    "#         dfs(root)\n",
    "#         return [l[0] for l in d.values() if len(l) > 1]\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.hash, self.count = {}, {}  # hash用来把子树映射成某个数字，count用来统计子树的个数\n",
    "        self.cnt = 1\n",
    "        self.res = []\n",
    "\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        if not root:\n",
    "            return root\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root):\n",
    "        \"\"\"\n",
    "        :param root: 以root为根结点的子树\n",
    "        :return: 以root为根结点的子树的字符串表示，用'1'，'2'，'3'，'4'，'5' ... 来表示不同的子树\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"1\"  # 1表示空子树，随后的子树用2，3，4，5，...来表示\n",
    "        left, right = self.dfs(root.left), self.dfs(root.right)  # left和right都对应着某个数字\n",
    "        subtree = left + \" \" + str(root.val) + \" \" + right\n",
    "        if subtree not in self.hash:\n",
    "            self.cnt += 1\n",
    "            self.hash[subtree] = self.cnt  # 第一轮哈希映射，把树的字符串表示映射成某个数字\n",
    "        t = self.hash[subtree]\n",
    "        self.count[t] = self.count.get(t, 0) + 1  # 第二轮哈希映射，统计每棵子树出现的次数\n",
    "        if self.count[t] == 2:  # 出现次数刚好等于2时，把节点添加到res中，避免重复\n",
    "            self.res.append(root)\n",
    "        return str(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        d = collections.defaultdict(int)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            \n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "\n",
    "            t = ((node.val, l, r))\n",
    "            d[t] += 1\n",
    "            if d[t] == 2:\n",
    "                ans.append(node)\n",
    "            \n",
    "            return t\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        trees = {}\n",
    "        count = {}\n",
    "        ans = []\n",
    "        def getuid(node):\n",
    "            if node:\n",
    "                tempkey = (node.val,getuid(node.left),getuid(node.right))\n",
    "                if tempkey not in count:\n",
    "                    count[tempkey] = 1\n",
    "                else:\n",
    "                    count[tempkey] += 1\n",
    "                if count[tempkey] == 2:\n",
    "                    ans.append(node)\n",
    "                return tempkey\n",
    "        getuid(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node) -> string:\n",
    "\n",
    "        if node is None:\n",
    "            return \"\"\n",
    "\n",
    "        code_left = self.dfs(node.left)\n",
    "        code_right = self.dfs(node.right)\n",
    "\n",
    "        code = hash(str(node.val) + \"#\" + str(code_left) + \"*\" + str(code_right))\n",
    "        if code in self.subtrees and code not in self.res:\n",
    "            self.res[code] = node\n",
    "        self.subtrees.add(code)\n",
    "        return code\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.subtrees = set()\n",
    "        self.res = {}\n",
    "        self.dfs(root)\n",
    "        return self.res.values()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        seen = {}\n",
    "        idx = 0\n",
    "        repeat = set()\n",
    "\n",
    "        def dfs(node):\n",
    "\n",
    "            nonlocal idx\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            cur = (node.val, dfs(node.left), dfs(node.right))\n",
    "\n",
    "            if cur in seen:\n",
    "                node, index = seen[cur]\n",
    "                repeat.add(node)\n",
    "                return index \n",
    "            \n",
    "            else:\n",
    "                idx += 1\n",
    "                seen[cur] = (node, idx)\n",
    "                return idx\n",
    "\n",
    "        dfs(root)\n",
    "        #print(seen)\n",
    "        return list(repeat)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.index = 0\n",
    "        treesDic = {}\n",
    "\n",
    "        self.ans = []\n",
    "\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            tree = (root.val, traverse(root.left), traverse(root.right))\n",
    "            if tree in treesDic:\n",
    "                idx, seentime = treesDic[tree]\n",
    "                treesDic[tree] = (idx, seentime+1)\n",
    "                if seentime==1:\n",
    "                    self.ans.append(root)\n",
    "                return idx\n",
    "            else:\n",
    "                self.index += 1\n",
    "                treesDic[tree] = (self.index, 1)\n",
    "                return self.index\n",
    "        \n",
    "        traverse(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.seen = {}\n",
    "        self.idx_cnt = 0\n",
    "        self.duplicate = {}\n",
    "        self.dfs(root)\n",
    "        return self.duplicate.values()\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        tri = (root.val, self.dfs(root.left), self.dfs(root.right))\n",
    "        if tri in self.seen:\n",
    "            idx = self.seen[tri]\n",
    "            if idx not in self.duplicate:\n",
    "                self.duplicate[idx] = root\n",
    "            return idx\n",
    "        self.idx_cnt += 1\n",
    "        self.seen[tri] = self.idx_cnt\n",
    "        return self.idx_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "        self.res = []\n",
    "        self.idx = 0\n",
    "\n",
    "    def post(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        left_idx = None\n",
    "        right_idx = None\n",
    "        if root.left:\n",
    "            left_idx = self.post(root.left)\n",
    "        if root.right:\n",
    "            right_idx = self.post(root.right)\n",
    "\n",
    "        c = (root.val, left_idx, right_idx)\n",
    "\n",
    "        if c in self.d:\n",
    "            if self.d[c][1] == 0:\n",
    "                self.res.append(root)\n",
    "                self.d[c][1] += 1\n",
    "            return self.d[c][0]\n",
    "        else:\n",
    "            self.d[c] = [self.idx, 0]\n",
    "            self.idx += 1\n",
    "            return self.idx - 1\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.post(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.index = 0\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        vis = dict()\n",
    "        duplicated = set()\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            else:\n",
    "                cur_tree = (node.val,dfs(node.left),dfs(node.right))\n",
    "                print(cur_tree)\n",
    "                if cur_tree in vis:\n",
    "                    idx,nd = vis[cur_tree]\n",
    "                    duplicated.add(nd)\n",
    "                    return idx\n",
    "                else:\n",
    "                    self.index +=1\n",
    "                    vis[cur_tree] = (self.index,node)\n",
    "                    return self.index\n",
    "\n",
    "        dfs(root)\n",
    "        return list(duplicated)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            tri = (node.val, dfs(node.left), dfs(node.right))\n",
    "            if tri in seen:\n",
    "                (tree, index) = seen[tri]\n",
    "                repeat.add(tree)\n",
    "                print(\"repeat=\",repeat)\n",
    "                return index\n",
    "            else:\n",
    "                nonlocal idx\n",
    "                idx += 1\n",
    "                seen[tri] = (node, idx)\n",
    "   \n",
    "                return idx\n",
    "        \n",
    "        idx = 0\n",
    "        seen = {}\n",
    "        repeat = set()\n",
    "\n",
    "        dfs(root)\n",
    "    \n",
    "        return list(repeat)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        fe = {}\n",
    "        def build(root: Optional[TreeNode]):\n",
    "            if root is None:\n",
    "                return (0, 0, 0)\n",
    "            l, r  = build(root.left), build(root.right)\n",
    "            fe[root] = (max(l[0], r[0]) + 1, l[1] + r[1] + 1, l[1] - r[1])\n",
    "            return fe[root]\n",
    "        build(root)\n",
    "\n",
    "\n",
    "        def checkEq(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:\n",
    "            if (left is None) ^ (right is None):\n",
    "                return False\n",
    "            if left is None:\n",
    "                return True\n",
    "            if fe[left] != fe[right]:\n",
    "                return False\n",
    "            return left.val == right.val and checkEq(left.left, right.left) and checkEq(left.right, right.right)\n",
    "             \n",
    "        nodes = []\n",
    "        dups = []\n",
    "        def add(root: Optional[TreeNode]):\n",
    "            if root is None:\n",
    "                return\n",
    "            for n in nodes:\n",
    "                if checkEq(n[0], root):\n",
    "                    if not n[1]:\n",
    "                        dups.append(root)\n",
    "                        n[1] = True\n",
    "                    break\n",
    "            else:\n",
    "                nodes.append([root, False])\n",
    "            add(root.left)\n",
    "            add(root.right)\n",
    "        add(root.left), add(root.right)\n",
    "        return dups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "\n",
    "\n",
    "        def preiter(root):\n",
    "            yield (root.val)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left)))\n",
    "                yield from res\n",
    "            else:\n",
    "                res.append(None)\n",
    "                \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right)))\n",
    "                yield from res\n",
    "            else:\n",
    "                res.append(None)\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            # print(key)\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "            # val = counter.setdefault(key,0) + 1\n",
    "            # counter[key] = val\n",
    "            # ref.setdefault(key,[]).append(valu)\n",
    "            # ref[key] = value\n",
    "\n",
    "        def preiter(root,key=''):\n",
    "            yield (root.val, key)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left,'l')))\n",
    "                # update((root.val, *res),root.left)\n",
    "                yield from res\n",
    "            \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right,'r')))\n",
    "                # update((root.val, *res),root.right)\n",
    "                yield from res\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "        \n",
    "        candidate = []\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#     1\n",
    "#   2   3\n",
    "#  4 x 2 4\n",
    "# x x 4   \n",
    "# 当且仅当子树相同时，两棵树相同\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        counter = {}\n",
    "        ref = {}\n",
    "        def update(key,value):\n",
    "            counter.setdefault(key,[]).append(value)\n",
    "\n",
    "\n",
    "        def preiter(root,key=''):\n",
    "            yield (root.val, key)\n",
    "            # update((root.val,),root)\n",
    "            res = [root.val]\n",
    "            if root.left is not None:\n",
    "                res.append(tuple(preiter(root.left,'l')))\n",
    "                yield from res\n",
    "            \n",
    "            if root.right is not None:\n",
    "                res.append(tuple(preiter(root.right,'r')))\n",
    "                yield from res\n",
    "            update(tuple(res),root)\n",
    "\n",
    "        list(preiter(root))\n",
    "\n",
    "        res = []\n",
    "        for k,v in counter.items():\n",
    "            if len(v) > 1:\n",
    "                res.append(v[0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.result = []\n",
    "        self.trees = dict()\n",
    "        self.treverse(root)\n",
    "        return self.result\n",
    "    \n",
    "    def treverse(self, root):\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        \n",
    "        left_tree = self.treverse(root.left)\n",
    "        right_tree = self.treverse(root.right)\n",
    "\n",
    "        tree = left_tree + \"|\" + right_tree + \"|\" + str(root.val)\n",
    "\n",
    "        n = self.trees.get(tree, 0)\n",
    "        if n == 1:\n",
    "            self.result.append(root)\n",
    "        \n",
    "        if tree in self.trees:\n",
    "            self.trees[tree] += 1\n",
    "        else:\n",
    "            self.trees[tree] = 1\n",
    "        return tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, tree_map):\n",
    "        if root == None:\n",
    "            return \"\"\n",
    "        res = str(root.val)\n",
    "        if root.left:\n",
    "            left_res = self.dfs(root.left, tree_map)\n",
    "            res = left_res + \"-\" + res\n",
    "        if root.right:\n",
    "            right_res = self.dfs(root.right, tree_map)\n",
    "            res = res + (\"+\" + right_res)\n",
    "        tree_map[res].append(root)\n",
    "        return res\n",
    "    \n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        tree_map = defaultdict(list)\n",
    "        res = self.dfs(root, tree_map)\n",
    "        res = []\n",
    "        \n",
    "        for rep, sub_roots in tree_map.items():\n",
    "            if len(sub_roots) >= 2:\n",
    "                res.append(sub_roots[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        subtree_dict = collections.defaultdict(int)\n",
    "        self.res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return \"\"\n",
    "            left = traverse(root.left)\n",
    "            right = traverse(root.right)\n",
    "            sub_res = str(root.val) + \" \" + left + \" \" + right\n",
    "            subtree_dict[sub_res] += 1\n",
    "            if subtree_dict[sub_res] == 2:\n",
    "                self.res.append(root)\n",
    "            return sub_res\n",
    "        traverse(root)\n",
    "        return self.res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        has = {}\n",
    "        ans=set()\n",
    "        def findastring(node,s=''):\n",
    "            if node is None:\n",
    "                return 'N'\n",
    "            elif node.left is None and node.right is None:\n",
    "                s+='m'+str(node.val)\n",
    "            else:\n",
    "                s+='m'+str(node.val)\n",
    "                s+=findastring(node.left)\n",
    "                s+=findastring(node.right)\n",
    "            if s not in has:\n",
    "                has[s]=node\n",
    "            else:\n",
    "                ans.add(has[s])\n",
    "            return s\n",
    "        findastring(root)\n",
    "        return list(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:\n",
    "        d = collections.defaultdict(list)\n",
    "        def dfs(root):\n",
    "            if not root: return ''\n",
    "            s = ' '.join([str(root.val), dfs(root.left), dfs(root.right)])\n",
    "            d[s].append(root)\n",
    "            return s\n",
    "        dfs(root)\n",
    "        return [l[0] for l in d.values() if len(l) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.node = ()\n",
    "        self.res_tmp = []\n",
    "        self.res = []\n",
    "\n",
    "    def postorder(self, root):\n",
    "        if not root:\n",
    "            return ''\n",
    "        left = self.postorder(root.left)\n",
    "        right = self.postorder(root.right)\n",
    "        link = str(root.val) + ',' + left + ',' + right\n",
    "        if link in self.node:\n",
    "            if link not in self.res_tmp:\n",
    "                self.res_tmp.append(link)\n",
    "                self.res.append(root)\n",
    "        else:\n",
    "            self.node += (link,)\n",
    "        return link\n",
    "    def findDuplicateSubtrees(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        self.postorder(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        d = collections.defaultdict(int)\n",
    "        res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return '#'\n",
    "            l = traverse(root.left)\n",
    "            r = traverse(root.right)\n",
    "            signature = l + ',' + r + ',' + str(root.val)\n",
    "            if d[signature] == 1:\n",
    "                print(root.val)\n",
    "                res.append(root)\n",
    "            d[signature] += 1\n",
    "            return l + ',' + r + str(root.val)\n",
    "\n",
    "        traverse(root)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ\n",
    "# 跟序列化二叉树有关，序列化二叉树，就是把二叉树按照前或者中序或者后续遍历出来，写进字符串里\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 定义一个字典来存储所有子树以及出现的次数\n",
    "        self.memo = {}\n",
    "        # 定义一个列表来存储重复的子树根节点\n",
    "        self.res = []\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    # 辅助函数\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return \"#\"\n",
    "        \n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        \n",
    "        subTree = left + \",\" + right + \",\" + str(root.val)\n",
    "        \n",
    "        freq = self.memo.get(subTree, 0)\n",
    "        # 多次重复也只会被加入结果集一次\n",
    "        # 解释下这里==1的原因：第一次有subTree时，上一句代码将它初始化为0，然后self.memo[subTree] = freq + 1变为了1。\n",
    "        # 等到第二次，这个subTree又出现了（第二次出现），然后发现freq==1(上一次的)，这就说明重复出现了，好，把对应的root加进res。self.memo[subTree] = freq + 1变为2\n",
    "        # 等到第三次，freq已经变为2，不满足freq == 1的条件，不会加进res（因为之前已经加过了，这里就保证了不会重复）\n",
    "        if freq == 1:\n",
    "            self.res.append(root)\n",
    "        # 给子树对应的出现次数加一\n",
    "        self.memo[subTree] = freq + 1\n",
    "        # 这里不能用self.memo[subTree] += 1，因为第一次的时候subTree还不存在，会报错\n",
    "        return subTree\n",
    "\n",
    "\n",
    "\n",
    "# # 定义一个字典来存储所有子树以及出现的次数\n",
    "# memo = {}\n",
    "# # 定义一个列表来存储重复的子树根节点\n",
    "# res = []\n",
    "\n",
    "# # 主函数\n",
    "# def findDuplicateSubtrees(root):\n",
    "#     traverse(root)\n",
    "#     return res\n",
    "\n",
    "# # 辅助函数\n",
    "# def traverse(root):\n",
    "#     if root is None:\n",
    "#         return \"#\"\n",
    "    \n",
    "#     left = traverse(root.left)\n",
    "#     right = traverse(root.right)\n",
    "    \n",
    "#     subTree = left + \",\" + right + \",\" + str(root.val)\n",
    "    \n",
    "#     freq = memo.get(subTree, 0)\n",
    "#     # 多次重复也只会被加入结果集一次\n",
    "#     if freq == 1:\n",
    "#         res.append(root)\n",
    "#     # 给子树对应的出现次数加一\n",
    "#     memo[subTree] = freq + 1\n",
    "#     return subTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        ans = []\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        root_dict = dict()\n",
    "        def fun(root):\n",
    "            if root is None:\n",
    "                return '#'\n",
    "            \n",
    "            cur_sub = str(root.val) + ',' + fun(root.left) + ',' + fun(root.right)\n",
    "            if cur_sub not in root_dict:\n",
    "                #print('cur sub is :', cur_sub)\n",
    "                root_dict[cur_sub] = root\n",
    "            else:\n",
    "                nonlocal ans\n",
    "                if root_dict[cur_sub] not in ans:\n",
    "                    ans.append(root_dict[cur_sub])\n",
    "            \n",
    "            return cur_sub\n",
    "\n",
    "        \n",
    "        fun(root)\n",
    "        print('ans is: ', ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res = []\n",
    "        def serilaze(root, res) -> str:\n",
    "            if root is None:\n",
    "                res += ' ,'\n",
    "                return res\n",
    "            else:\n",
    "                res += str(root.val)\n",
    "                res += ','\n",
    "                return res + serilaze(root.left, '') + serilaze(root.right, '')\n",
    "        dic = {}\n",
    "        print(serilaze(root, ''))\n",
    "        def traversal(root) -> None:\n",
    "            if root is None:\n",
    "                return \n",
    "            if serilaze(root, '') not in dic:\n",
    "                dic[serilaze(root, '')] = root\n",
    "            else:\n",
    "                res.append(dic[serilaze(root, '')])\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "        return set(res)\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node: Optional[TreeNode]):\n",
    "        if node == None:\n",
    "            return [\"#\"]\n",
    "        left_path = self.dfs(node.left)\n",
    "        right_path = self.dfs(node.right)\n",
    "        path = left_path + right_path + [f\"{node.val}\"]\n",
    "        path_str = \" \".join(path)\n",
    "        if path_str not in self.hash_set:\n",
    "            self.hash_set.add(path_str)\n",
    "        else:\n",
    "            self.ans[path_str] = node\n",
    "        return path\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.hash_set = set()\n",
    "        self.ans = dict()\n",
    "        self.dfs(root)\n",
    "        return list(v for v in self.ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def serialze(node):\n",
    "            nonlocal vis, res\n",
    "            if not node:\n",
    "                return ''\n",
    "            \n",
    "            s = str(node.val) + '(' + serialze(node.left) + ')(' + serialze(node.right) + ')'\n",
    "            if s in vis and vis[s] == 1:\n",
    "                res.append(node)\n",
    "            vis[s] += 1\n",
    "            return s\n",
    "\n",
    "        vis = defaultdict(int)\n",
    "        res = []\n",
    "        serialze(root)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node: Optional[TreeNode]) -> str:\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            \n",
    "            serial = \"\".join([str(node.val), \"(\", dfs(node.left), \")(\", dfs(node.right), \")\"])\n",
    "            if (tree := seen.get(serial, None)):\n",
    "                repeat.add(tree)\n",
    "            else:\n",
    "                seen[serial] = node\n",
    "            return serial\n",
    "        \n",
    "        seen = dict()\n",
    "        repeat = set()\n",
    "\n",
    "        dfs(root)\n",
    "        return list(repeat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            line = \"\".join([str(node.val), \"(\", dfs(node.left), \")(\", dfs(node.right), \")\"])\n",
    "            if (tree := seen.get(line, None)):\n",
    "                repeat.add(tree)\n",
    "            else:\n",
    "                seen[line] = node\n",
    "            return line\n",
    "\n",
    "        seen = {}\n",
    "        repeat = set()\n",
    "        dfs(root)\n",
    "        return list(repeat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                return \"\"\n",
    "            else:\n",
    "                s = str(node.val)+f\"({dfs(node.left)})({dfs(node.right)})\"\n",
    "                if hs[s] and s not in nret:\n",
    "                    nret.add(s)\n",
    "                    ret.add(node)\n",
    "                else:\n",
    "                    hs[s] = True\n",
    "                return s\n",
    "\n",
    "        hs = defaultdict(lambda: False)\n",
    "        nret = set()\n",
    "        ret = set()\n",
    "        dfs(root)\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, root, subtree_map):\n",
    "        if root is None:\n",
    "            return \"N\"\n",
    "        l_ret = self.traverse(root.left, subtree_map)\n",
    "        r_ret = self.traverse(root.right, subtree_map)\n",
    "        if l_ret != \"N\" and l_ret != \"(N#N)\":\n",
    "            if l_ret not in subtree_map:\n",
    "                subtree_map[l_ret] = []\n",
    "            subtree_map[l_ret].append(root.left)\n",
    "        if r_ret != \"N\" and r_ret != \"(N#N)\":\n",
    "            if r_ret not in subtree_map:\n",
    "                subtree_map[r_ret] = []\n",
    "            subtree_map[r_ret].append(root.right)\n",
    "        #print(subtree_map)\n",
    "        ret = f\"({l_ret}#{root.val}#{r_ret})\"\n",
    "        return ret\n",
    "        \n",
    "\n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        subtree_map = {}\n",
    "        self.traverse(root, subtree_map)\n",
    "        dup_subtrees = []\n",
    "        for k in subtree_map:\n",
    "            if len(subtree_map[k]) > 1:\n",
    "                dup_subtrees.append(subtree_map[k][0])\n",
    "        return dup_subtrees\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "\n",
    "        self.dic = {}\n",
    "        self.res = []\n",
    "\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return '#'\n",
    "            left = func(root.left)\n",
    "            right = func(root.right)\n",
    "            s = f\"{left}, {right}, {root.val}\"\n",
    "\n",
    "            freq = self.dic.get(s, 0)\n",
    "            if freq == 1:\n",
    "                self.res.append(root)\n",
    "            self.dic[s] = freq+1\n",
    "            return s \n",
    "\n",
    "        func(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res_dict = {}\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            pre = str(root.val) + 'l' + left + 'r' + right\n",
    "            mid = 'l' + left + str(root.val) + 'r' + right\n",
    "\n",
    "            key = pre + '_' + mid\n",
    "            if key not in res_dict:\n",
    "                res_dict[key] = [root]\n",
    "            else:\n",
    "                res_dict[key].append(root)\n",
    "\n",
    "            return pre\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "        for value in res_dict.values():\n",
    "            if len(value) >= 2:\n",
    "                res.append(value[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        res_dict = {}\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            pre = str(root.val) + 'l' + left + 'r' + right\n",
    "            mid = 'l' + left + str(root.val) + 'r' + right\n",
    "\n",
    "            key = pre + '_' + mid \n",
    "            if len(res_dict.get(key, [])) == 1:\n",
    "                res.append(root)\n",
    "            if key not in res_dict:\n",
    "                res_dict[key] = [root]\n",
    "            else:\n",
    "                res_dict[key].append(root)\n",
    "\n",
    "            return pre\n",
    "\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.count = {}\n",
    "        self.res = []\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 'null,'\n",
    "        rep = f'{root.val},'\n",
    "        rep += self.dfs(root.left)\n",
    "        rep += self.dfs(root.right)\n",
    "        self.count[rep] = self.count.get(rep, 0) + 1\n",
    "        if self.count[rep] == 2:\n",
    "            self.res.append(root)\n",
    "        return rep\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        \"\"\"\n",
    "        回傳重複的 tree (數值和結構要一樣)\n",
    "        1. 如果 tree 的架構是一樣的, 那它的 subtree 架構也是一樣的\n",
    "           [2, 4] subtree\n",
    "           [4]    subtree 的 subtree\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        暴力法: O(n^3)\n",
    "        如果要每個 node 都走過一次\n",
    "        每個 subtree 都要走過一次, 都要比過一次\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        把 tree 變成一個\"字串\"\n",
    "\n",
    "        1. 對每個 subtree 都把它變成一個 string (serialization)\n",
    "\n",
    "        2. 用 preorder (其他也可以)\n",
    "\n",
    "        3. 用 hashmap 紀錄每個 subtree\n",
    "           (key 就是 subtree 的 string)\n",
    "           如果一個 key 有兩個 node, 那就代表這個 subtree 是重複的\n",
    "\n",
    "        4. 從 root 開始執行 dfs, 建立每個 subtree 的 string\n",
    "           (要把 \"null\" 的部分加進去, 這樣才能把 subtree \"結構\"做出來)\n",
    "            \n",
    "            e.g. 同樣是 1, 2, 3, 但是兩個 subtree 架構都不一樣!\n",
    "            a. [1, 2, Null, Null, 3, Null, Null]\n",
    "            b. [1, Null, 2, Null, 3, Null, Null]\n",
    "\n",
    "        5. time: O(n*n)\n",
    "           有 n 個 node, 每個 node 都要做出 n 個 string(最大)\n",
    "        \"\"\"\n",
    "\n",
    "        # 想到這招真的很厲害...\n",
    "        hashmap = defaultdict(list)\n",
    "        result  = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"null\"\n",
    "\n",
    "            s = str(node.val) + \",\" + dfs(node.left) + \",\" + dfs(node.right)\n",
    "\n",
    "            # 如果這個 string 已經在 hashmap 裡面了\n",
    "            if len(hashmap[s]) == 1:\n",
    "                result.append(node) # 把當前的 node 當作 root 加入到 result\n",
    "            hashmap[s].append(node) # 也加入到 hashmap 對應的 string\n",
    "            print(f\"{s=}\")\n",
    "            return s\n",
    "        \n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "\n",
    "        \"\"\"\n",
    "        回傳重複的 tree (數值和結構要一樣)\n",
    "        1. 如果 tree 的架構是一樣的, 那它的 subtree 架構也是一樣的\n",
    "           [2, 4] subtree\n",
    "           [4]    subtree 的 subtree\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        暴力法: O(n^3)\n",
    "        如果要每個 node 都走過一次\n",
    "        每個 subtree 都要走過一次, 都要比過一次\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        把 tree 變成一個\"字串\"\n",
    "\n",
    "        1. 對每個 subtree 都把它變成一個 string (serialization)\n",
    "\n",
    "        2. 用 preorder (其他也可以)\n",
    "\n",
    "        3. 用 hashmap 紀錄每個 subtree\n",
    "           (key 就是 subtree 的 string)\n",
    "           如果一個 key 有兩個 node, 那就代表這個 subtree 是重複的\n",
    "\n",
    "        4. 從 root 開始執行 dfs, 建立每個 subtree 的 string\n",
    "           (要把 \"null\" 的部分加進去, 這樣才能把 subtree \"結構\"做出來)\n",
    "            \n",
    "            e.g. 同樣是 1, 2, 3, 但是兩個 subtree 架構都不一樣!\n",
    "            a. [1, 2, Null, Null, 3, Null, Null]\n",
    "            b. [1, Null, 2, Null, 3, Null, Null]\n",
    "\n",
    "        5. time: O(n*n)\n",
    "           有 n 個 node, 每個 node 都要做出 n 個 string(最大)\n",
    "        \"\"\"\n",
    "\n",
    "        # 想到這招真的很厲害...\n",
    "        hashmap = defaultdict(list)\n",
    "        result  = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return \"null\"\n",
    "\n",
    "            s = str(node.val) + \",\" + dfs(node.left) + \",\" + dfs(node.right)\n",
    "\n",
    "            # 如果這個 string 已經在 hashmap 裡面了\n",
    "            if len(hashmap[s]) == 1:\n",
    "                result.append(node) # 把當前的 node 當作 root 加入到 result\n",
    "            hashmap[s].append(node) # 也加入到 hashmap 對應的 string\n",
    "            print(f\"{s=}\")\n",
    "            return s\n",
    "        \n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        history = {}\n",
    "        ans = []\n",
    "        def search(root, history, ans):\n",
    "            if root == None:\n",
    "                return 'n '\n",
    "            else:\n",
    "                s = ''\n",
    "                s += str(root.val) + ' '\n",
    "                s += search(root.left, history, ans) + ' '\n",
    "                s += search(root.right, history, ans) + ' '\n",
    "\n",
    "                # print(s)\n",
    "                if s in history:\n",
    "                    if history[s] == 1:\n",
    "                        ans.append(root)\n",
    "                    history[s] += 1\n",
    "                else:\n",
    "                    history[s] = 1\n",
    "                \n",
    "                return s\n",
    "        \n",
    "        search(root, history, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        global visited_node \n",
    "        visited_node = set()\n",
    "        global overlap_root_node\n",
    "        overlap_root_node = dict()\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            string_treenode = f'{root.val}({dfs(root.left)},{dfs(root.right)})'\n",
    "            if string_treenode in visited_node:\n",
    "                overlap_root_node[string_treenode] = (root)\n",
    "            else:\n",
    "                visited_node.add(string_treenode)\n",
    "            #print(string_treenode)\n",
    "            return string_treenode\n",
    "        \n",
    "        dfs(root)\n",
    "        #print(overlap_root_node)\n",
    "\n",
    "        return list(overlap_root_node.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.dct = {}\n",
    "        self.dfs(root)\n",
    "        return [v[0] for v in self.dct.values() if len(v) > 1]\n",
    "\n",
    "    \n",
    "    def dfs(self, head):\n",
    "        if not head:\n",
    "            return \"(#)\"\n",
    "        \n",
    "        ret = str(head.val)\n",
    "\n",
    "        ret = ret + self.dfs(head.left) \n",
    "        ret = ret + self.dfs(head.right)\n",
    "\n",
    "        ret = f\"({ret})\"\n",
    "        if ret not in self.dct:\n",
    "            self.dct[ret] = []\n",
    "        self.dct[ret].append(head)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        d={}\n",
    "        ans=[]\n",
    "        if not root: return []\n",
    "        def dfs(root):\n",
    "            if not root: return ''\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            chain=left+','+right+','+str(root.val)\n",
    "            if chain not in d:\n",
    "                d[chain]=1\n",
    "            else:\n",
    "                d[chain]+=1\n",
    "            if d[chain]==2:\n",
    "                ans.append(root)\n",
    "            return chain\n",
    "        tree=dfs(root)\n",
    "        print(tree)\n",
    "        print(d)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        self.ans = []\n",
    "        self.cnt = defaultdict(int)\n",
    "        # @lru_cache(None)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 'None'\n",
    "            node = f'{root.val}, {dfs(root.left)}, {dfs(root.right)}'\n",
    "            self.cnt[node] += 1   \n",
    "            if self.cnt[node] == 2:\n",
    "                self.ans.append(root)                     \n",
    "            return node\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.treeNodeMap = {}\n",
    "        self.treeNodeSet = []    \n",
    "\n",
    "    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:\n",
    "        \n",
    "        self.visitTreeNode(root)\n",
    "        return list(self.treeNodeMap.values())\n",
    "        \n",
    "\n",
    "    \n",
    "\n",
    "    def visitTreeNode(self, node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        treeNodeKey = f'{node.val}_({self.visitTreeNode(node.left)}_{self.visitTreeNode(node.right)})'\n",
    "        if treeNodeKey in self.treeNodeSet:\n",
    "            self.treeNodeSet.append(treeNodeKey)\n",
    "            self.treeNodeMap[treeNodeKey] = node\n",
    "        else:\n",
    "            self.treeNodeSet.append(treeNodeKey)\n",
    "\n",
    "\n",
    "        return treeNodeKey\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        # 快慢指针，有duplicate会有环\n",
    "        slow, fast = 0, 0\n",
    "        while True:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "            if slow == fast:\n",
    "                break\n",
    "        slow = 0 # 找环的入口\n",
    "        while True:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[fast]\n",
    "            if slow == fast:\n",
    "                return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        slow, fast = 0, 0\n",
    "        while True:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "            if slow == fast:\n",
    "                break\n",
    "        \n",
    "        fast = 0\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[fast]\n",
    "        \n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        high = len(nums)-1\n",
    "        low  = 0\n",
    "        mid  = (high+low)/2\n",
    "        \n",
    "        while high - low > 1 :\n",
    "            count = 0\n",
    "            for k in nums:\n",
    "                if k<=mid :\n",
    "                    count += 1\n",
    "            if count > mid:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "            mid = (high+low)/2\n",
    "        return int(high)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        visited = set()\n",
    "        for num in nums:\n",
    "            if num in visited:\n",
    "                return num\n",
    "            visited.add(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if not nums:\n",
    "        #     return None\n",
    "        # nums.sort()\n",
    "        # for index in range(len(nums)-1):\n",
    "        #     if nums[index] == nums[index + 1]:\n",
    "        #         return nums[index]\n",
    "        # return None\n",
    "        \n",
    "#         left, right = 0, len(nums)\n",
    "        \n",
    "#         while left < right:\n",
    "#             mid = left + (right - left)//2\n",
    "#             count = 0\n",
    "#             for x in nums:\n",
    "#                 if x <= mid:\n",
    "#                     count += 1\n",
    "#             if count <= mid:\n",
    "#                 left = mid+1\n",
    "#             else:\n",
    "#                 right = mid\n",
    "        \n",
    "#         return right\n",
    "        \n",
    "        \n",
    "        slow = nums[0]\n",
    "        fast = nums[nums[0]]\n",
    "        while slow != fast:\n",
    "            fast = nums[nums[fast]]\n",
    "            slow = nums[slow]\n",
    "        fast = 0\n",
    "        while slow != fast:\n",
    "            fast = nums[fast]\n",
    "            slow = nums[slow]\n",
    "        return fast\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: 'List[int]') -> 'int':\n",
    "        if not nums:\n",
    "            return\n",
    "        dict = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in dict:\n",
    "                return num\n",
    "            else:\n",
    "                dict[num] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: 'List[int]') -> 'int':\n",
    "        counts = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in counts.keys():\n",
    "                counts[nums[i]] = 1\n",
    "            else:\n",
    "                counts[nums[i]] += 1\n",
    "\n",
    "        for key in counts.keys():\n",
    "            if counts[key] > 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        t = set(nums)\n",
    "        return int((sum(nums)-sum(t))/(len(nums)-len(t)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dict1=dict(Counter(nums))\n",
    "        return [i for i in dict1 if dict1[i]>=2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        low = 1\n",
    "        higt = max(nums)\n",
    "        while low < higt:\n",
    "            med = (low+higt) // 2\n",
    "            num = len([i for i in range(len(nums)) if nums[i] <= med])\n",
    "            if num > med:\n",
    "                higt = med    \n",
    "            else:\n",
    "                low = med+1\n",
    "        return low "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return (sum(nums)-sum(set(nums)))//(len(nums) - len(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    def findDuplicate(self, nums: 'List[int]') -> 'int':\n",
    "        #使用O(n)额外空间解法\n",
    "        if not nums:\n",
    "            return\n",
    "        numsTemp = [0]*(len(nums)+1)\n",
    "        for num in nums:\n",
    "            if numsTemp[num] == 1:\n",
    "                return num\n",
    "            else:\n",
    "                numsTemp[num] = 1\n",
    "    \"\"\"\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return (sum(nums)-sum(set(nums)))//(len(nums) - len(set(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        slow, fast, start = 0, 0, 0\n",
    "        while True:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "            if slow == fast:\n",
    "                break\n",
    "        while slow != start:\n",
    "            start = nums[start]\n",
    "            slow = nums[slow]\n",
    "        return start\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        if not nums:return\n",
    "        fast = slow = 0\n",
    "        while True:\n",
    "            fast = nums[nums[fast]]\n",
    "            slow = nums[slow]\n",
    "            if fast == slow:\n",
    "                fast = 0\n",
    "                while nums[slow]!=nums[fast]:\n",
    "                    fast = nums[fast]\n",
    "                    slow = nums[slow]\n",
    "                return nums[slow]\n",
    "        return \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 2:\n",
    "            return 1\n",
    "        slow = nums[0]\n",
    "        fast = nums[nums[0]]\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "        fast = 0\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[fast]\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        slow = nums[0]\n",
    "        fast = nums[nums[0]]\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "        fast = 0\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[fast]\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        dic = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if dic.get(nums[i]):\n",
    "                return nums[i]\n",
    "            else:\n",
    "                dic[nums[i]] = 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        left=1\n",
    "        right=len(nums)\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            cnt=0\n",
    "            for num in nums:\n",
    "                if num<=mid:\n",
    "                    cnt+=1\n",
    "            if cnt<=mid:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\r\n",
    "        k = len(nums)\r\n",
    "        for i in range(k):\r\n",
    "            while nums[i] != i + 1:\r\n",
    "                right_pos = nums[i] - 1\r\n",
    "                if nums[right_pos] == nums[i]:\r\n",
    "                    return nums[i]\r\n",
    "                else:\r\n",
    "                    nums[i], nums[right_pos] = nums[right_pos], nums[i]\r\n",
    "        return nums[k-1]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        table = collections.defaultdict(int)\n",
    "        for i in nums:\n",
    "            if table[i] == 1:\n",
    "                return i\n",
    "            else:\n",
    "                table[i] += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        adict = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in adict:\n",
    "                adict[nums[i]] = 1\n",
    "            else:\n",
    "                adict[nums[i]] += 1\n",
    "        for key,val in adict.items():\n",
    "            if val > 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        dict = {}\n",
    "        for i in nums:\n",
    "            if i in dict:\n",
    "                dict[i] = dict[i]+1\n",
    "            else:\n",
    "                dict[i] = 1\n",
    "        for i in dict:\n",
    "            if dict[i] >=2:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\r\n",
    "        numset = set()\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if nums[i] in numset:\r\n",
    "                return nums[i]\r\n",
    "            numset.add(nums[i])\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        xx = set(range(1, len(nums)))\n",
    "        for x in nums:\n",
    "            if x in xx:\n",
    "                xx.remove(x)\n",
    "            else:\n",
    "                return x\n",
    "        return -1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        xx = set(range(1, len(nums)))\n",
    "        for x in nums:\n",
    "            if x in xx:\n",
    "                xx.remove(x)\n",
    "            else:\n",
    "                return x\n",
    "        return -1        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        count = 0\n",
    "        for i in list(range(length))*11:\n",
    "            value = nums[i]\n",
    "            if value != i+1 and nums[value-1] != value:\n",
    "                temp = nums[value-1]\n",
    "                nums[value-1] = value\n",
    "                nums[i] = temp\n",
    "                count += 1\n",
    "            \n",
    "            if i == length:\n",
    "                if count == 0:\n",
    "                    break\n",
    "                else:\n",
    "                    count = 0\n",
    "        \n",
    "        for i in range(length):\n",
    "            if nums[i] != i+1:\n",
    "                return nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        dic = {i: nums.count(i) for i in set(nums)}\n",
    "        return max(dic, key = dic.get)\n",
    "        # return sum(nums)-sum(list())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        lt = [0] * len (nums)\n",
    "        dt = {key:value for key, value in zip(s, lt)}\n",
    "        for i in nums:\n",
    "            dt[i] += 1\n",
    "            if dt[i] > 1:\n",
    "                return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        hashmap={}\n",
    "        n=len(nums)-1\n",
    "        for i in range(1,n+1):\n",
    "            hashmap[i]=[]\n",
    "        for j in range(len(nums)):\n",
    "            hashmap[nums[j]].append(1)\n",
    "        for k in hashmap:\n",
    "            if len(hashmap[k])>1:\n",
    "                return k\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        res = [0]*(len(nums)-1)\n",
    "        for num in nums:\n",
    "            res[num-1] +=1\n",
    "        nums.clear()\n",
    "        for i, n in enumerate(res):\n",
    "            if n >= 2:\n",
    "                return i+1            \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        nums_len = len(nums)\n",
    "        count_1 = [0] * 32\n",
    "        count_2 = [0] * 32\n",
    "        for i in range(nums_len):\n",
    "            for j in range(32):\n",
    "                if nums[i] <= 0:\n",
    "                    break\n",
    "                count_2[j] += nums[i] % 2\n",
    "                nums[i] = nums[i] >> 1\n",
    "            for j in range(32):\n",
    "                if i <= 0:\n",
    "                    break\n",
    "                count_1[j] += i % 2\n",
    "                i = i >> 1\n",
    "\n",
    "\n",
    "\n",
    "        # print(count_1)\n",
    "        # print(count_2)\n",
    "        tag = 0\n",
    "        for j in range(32):\n",
    "            if count_1[j] < count_2[j]:\n",
    "                tag += (1 << j)\n",
    "        return tag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        while(i < len(nums)):\n",
    "            reIdx = nums[i] - 1\n",
    "            if(reIdx < 0):\n",
    "                i += 1\n",
    "            elif(nums[reIdx] > 0):\n",
    "                nums[i] = nums[reIdx]\n",
    "                nums[reIdx] = -1\n",
    "            else:\n",
    "                nums[reIdx] -= 1\n",
    "                nums[i] = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if(num < -1):\n",
    "                return idx + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        # left = min(nums)\n",
    "        # right = max(nums)\n",
    "        # while left < right:\n",
    "        #     mid = (left + right)//2\n",
    "        #     count = 0\n",
    "        #     for i in range(len(nums)):\n",
    "        #         if nums[i] <= mid:\n",
    "        #             count += 1\n",
    "        #     if count > mid:\n",
    "        #         right = mid\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        # return left\n",
    "\n",
    "        n = len(nums) - 1\n",
    "        bin_data = bin(n)\n",
    "        x = [0]*(len(bin_data) - 2)\n",
    "        y = [0]*(len(bin_data) - 2)\n",
    "        for i in range(n + 1):\n",
    "            bin1 = bin(i)\n",
    "            bin2 = bin(nums[i])\n",
    "            for i in range(len(bin1) - 2):\n",
    "                y[i] = y[i] + int(bin1[len(bin1) - i - 1])\n",
    "            for i in range(len(bin2) - 2):\n",
    "                x[i] = x[i] + int(bin2[len(bin2) - i - 1])\n",
    "        result = 0\n",
    "        for i in range(len(x)):\n",
    "            if x[i] > y[i]:\n",
    "                result = 2**i + result\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        begin = 0\n",
    "        while nums[begin] != 0:\n",
    "            tmp = nums[begin]\n",
    "            nums[begin] = 0\n",
    "            begin = tmp\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        idx = 0\n",
    "        while True:\n",
    "            if nums[idx] != -1:\n",
    "                tmp = nums[idx]\n",
    "                nums[idx] = -1\n",
    "                idx = tmp\n",
    "            else:\n",
    "                return idx\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        if not nums or len(nums) == 0:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<=0:\n",
    "                continue;\n",
    "            \n",
    "        \n",
    "            while nums[i] != i+1:\n",
    "                j = nums[i]-1\n",
    "                if nums[j]>0:\n",
    "                    nums[i],nums[j] = nums[j], -1\n",
    "                else:\n",
    "                    nums[i],nums[j] = 0, nums[j]-1\n",
    "                    break\n",
    "            \n",
    "            if nums[i] == i+1:\n",
    "                nums[i] = -1\n",
    "        \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<-1:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        if not nums or len(nums) == 0:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<=0:\n",
    "                continue;\n",
    "            \n",
    "        \n",
    "            while nums[i] != i+1:\n",
    "                j = nums[i]-1\n",
    "                if nums[j]>0:\n",
    "                    nums[i],nums[j] = nums[j], -1\n",
    "                else:\n",
    "                    nums[i],nums[j] = 0, nums[j]-1\n",
    "                    break\n",
    "            \n",
    "            if nums[i] == i+1:\n",
    "                nums[i] = -1\n",
    "        \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<-1:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        tem=0\n",
    "        i=0\n",
    "        tem=nums[0]\n",
    "        while i <len(nums) :\n",
    "            \n",
    "            if nums[tem] !=0:\n",
    "                \n",
    "                i=tem\n",
    "                tem=nums[i]\n",
    "                nums[i]=0\n",
    "                \n",
    "                \n",
    "                print(tem)\n",
    "            else:\n",
    "                return tem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        # 快慢指针法:将nums看作一个链表，nums[i]的下一个元素为nums[nums[i]-1]\n",
    "        slow, fast = nums[0], nums[nums[0]]\n",
    "        while slow != fast:\n",
    "            slow = nums[slow]\n",
    "            fast = nums[nums[fast]]\n",
    "        \n",
    "        slow = 0\n",
    "        while slow != fast:\n",
    "            slow = nums[slow] \n",
    "            fast = nums[fast]\n",
    "\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums):\n",
    "        p, pre = 0, -1\n",
    "        while p != -1:\n",
    "            p, pre = nums[p], p\n",
    "            nums[pre] = -1\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        f,s=0,0\n",
    "        while True:\n",
    "            f=nums[nums[f]]\n",
    "            s=nums[s]\n",
    "            if f==s:\n",
    "                break\n",
    "        t=0\n",
    "        while t!=s:\n",
    "            t=nums[t]\n",
    "            s=nums[s]\n",
    "        return t            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 不符合题意，修改了数组\n",
    "# class Solution:\n",
    "#     def findDuplicate(self, nums: List[int]) -> int:\n",
    "#         for num in nums:\n",
    "#             # 要加abs,可能前面已经修改过了\n",
    "#             if nums[abs(num)-1]>0:\n",
    "#                 nums[abs(num)-1]*=-1\n",
    "#             else:\n",
    "#                 return abs(num)\n",
    "\n",
    "# # 方法一：二分法\n",
    "# class Solution:\n",
    "#     def findDuplicate(self, nums: List[int]) -> int:\n",
    "#         left,right=0,len(nums)-1\n",
    "#         while left<=right:\n",
    "#             mid=(left+right)//2\n",
    "#             count=0\n",
    "#             for num in nums:\n",
    "#                 if num<=mid:\n",
    "#                     count+=1\n",
    "#             if count>mid:\n",
    "#                 right=mid-1\n",
    "#                 ans=mid\n",
    "#             else:\n",
    "#                 left=mid+1\n",
    "#         return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 方法二：快慢指针\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        slow,fast=0,0\n",
    "        # 和环形链表不一样的地方，因为可以确定链表一定有环\n",
    "        while True:\n",
    "            # 巧妙：用索引代表指针\n",
    "            slow=nums[slow]\n",
    "            fast=nums[nums[fast]]\n",
    "            if slow==fast:\n",
    "                break\n",
    "        fast=0\n",
    "        while slow != fast:\n",
    "            slow=nums[slow]\n",
    "            fast=nums[fast]\n",
    "        return slow\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        max_bit,n =max(nums).bit_length()-1,len(nums)\n",
    "        ans = 0\n",
    "        for i in range(max_bit,-1,-1):\n",
    "            mask = 1<<i\n",
    "            print(mask)\n",
    "            cnt1=0\n",
    "            for num in nums:\n",
    "                if mask&num:\n",
    "                    cnt1 += 1                \n",
    "            cnt2=0\n",
    "            for x in range(1,n):\n",
    "                if mask&x:\n",
    "                    cnt2 += 1\n",
    "            print(cnt1,cnt2)\n",
    "            if cnt1>cnt2:\n",
    "                ans|=mask;\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        for i in nums:\n",
    "            x=abs(i)-1\n",
    "            if nums[x]<0:\n",
    "                return x+1\n",
    "            nums[x]=-nums[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        # dic = {}\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] in dic.keys():\n",
    "        #         return nums[i]\n",
    "        #     else:\n",
    "        #         dic[nums[i]] = i \n",
    "        \n",
    "\n",
    "        # n, i = len(nums), 0\n",
    "        # while i < n:\n",
    "        #     t, idx = nums[i], nums[i] - 1\n",
    "        #     if nums[idx] == t:\n",
    "        #         if idx != i:\n",
    "        #             return t\n",
    "        #         i += 1\n",
    "        #     else:\n",
    "        #         nums[i], nums[idx] = nums[idx], nums[i]\n",
    "        # return -1\n",
    "\n",
    "\n",
    "        slow, fast = 0, 0\n",
    "        while True:\n",
    "            slow = nums[slow]           # 类比链表slow=slow.next\n",
    "            fast = nums[nums[fast]]     # 类比链表fast=fast.next.next\n",
    "            if fast == slow:    # 首次相遇点\n",
    "                break\n",
    "        \n",
    "        fast = 0                # fast回到起点\n",
    "        while slow != fast:     # 再次相遇点即为重复数字\n",
    "            slow = nums[slow]\n",
    "            fast = nums[fast]\n",
    "        \n",
    "        return fast\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        nums[:] = sorted(nums)\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==nums[i+1]:\n",
    "                return nums[i]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        print(nums)\n",
    "        ans = None\n",
    "        for i in range(0, n):\n",
    "            index = abs(nums[i])\n",
    "            if nums[index] < 0:\n",
    "                ans = index\n",
    "            else:\n",
    "                nums[index] *= -1\n",
    "        print(nums)\n",
    "\n",
    "        nums = [abs(num) for num in nums]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if nums[mid] == nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            elif len(nums[l:mid+1]) > len(list(set(nums[l:mid+1]))):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        numbers = set()\n",
    "        while nums!= []:\n",
    "            num =nums.pop()\n",
    "            if num in numbers:return num\n",
    "            numbers.add(num)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        # 方法3：hash\n",
    "        a = set()\n",
    "        for i in nums:\n",
    "            if i not in a:\n",
    "                a.add(i)\n",
    "            else:\n",
    "                return i\n",
    "            \n",
    "        \n",
    "        # 方法2：暴力(超时)\n",
    "        count1 = 0\n",
    "        numsSize = len(nums)\n",
    "        notNum = set()\n",
    "        while count1 < numsSize - 1:\n",
    "            if nums[count1] not in notNum:\n",
    "                count2 = count1 + 1\n",
    "                while count2 < numsSize:\n",
    "                    if nums[count1] == nums[count2]:\n",
    "                        return nums[count1] \n",
    "                    count2 += 1\n",
    "                notNum.add(nums[count1])\n",
    "                count1 += 1\n",
    "        \n",
    "\n",
    "        # 方法1：排序后遍历(修改了数组，所以需要其他方法)\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        numsSize = len(nums)\n",
    "        while count < numsSize:\n",
    "            if nums[count] == nums[count+1]:\n",
    "                return nums[count]\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        set1 = set()\n",
    "        for i in range(len(nums)):\n",
    "            lenpre = len(set1)\n",
    "            set1.add(nums[i])\n",
    "            if len(set1) == lenpre:\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for i in nums:\n",
    "            if i in s:\n",
    "                return i\n",
    "            else:\n",
    "                s.add(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        hashset = set()\n",
    "        for num in nums:\n",
    "            if num not in hashset:\n",
    "                hashset.add(num)\n",
    "            else:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        num_set = set()\n",
    "        for num in nums:\n",
    "            if num in num_set:\n",
    "                return num\n",
    "            num_set.add(num)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "\n",
    "        ha = set()\n",
    "\n",
    "        for num in nums:\n",
    "            if num in ha:\n",
    "                return num\n",
    "            ha.add(num)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        hmap = set()\n",
    "        for num in nums:\n",
    "            if num in hmap: \n",
    "                return num\n",
    "            hmap.add(num)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        nums_set=set()\n",
    "        for ind in nums:\n",
    "            if ind in nums_set:\n",
    "                return ind\n",
    "            else:\n",
    "                nums_set.add(ind)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        sn = list((sorted(nums)))+sorted(list(set(nums)))\n",
    "        l = 0\n",
    "        r = len(sn)\n",
    "        turn = 0\n",
    "        while l<m-1 and l+m<r:\n",
    "            if sn[l]==sn[l+m]:\n",
    "                l+=1\n",
    "            elif sn[l] !=sn[l+m]:\n",
    "                turn = 1\n",
    "                return(sn[l])\n",
    "        if turn == 0:\n",
    "            return sn[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "            else :\n",
    "                return i    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        num_map = defaultdict(int)\n",
    "        for n in nums:\n",
    "            if num_map[n] != 0:\n",
    "                return n\n",
    "            num_map[n] += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dic.keys():\n",
    "                return nums[i]\n",
    "            else:\n",
    "                dic[nums[i]] = i \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
